前缀和与差分
前言
本文只写公式，不证明。
下文中 d \large d d数组均表示差分数组， a \large a a数组均表示原数组， p r e \large pre pre数组均表示前缀和数组，下面让我们 l e t ′ s g o \large let's\ \ go let′s go
一维
d i = a i − a i − 1 a n = ∑ i = 1 n d i p r e n = ∑ i = 1 n a i = ∑ x = 1 n ∑ i = 1 x d i = ∑ i = 1 n d i × ( n − i + 1 ) \large d_i=a_i-a_{i-1} \\ \large a_n=\sum\limits_{i=1}^nd_i \\ \large pre_n=\sum\limits_{i=1}^n a_i=\sum\limits_{x=1}^n\sum\limits_{i=1}^x d_i=\sum\limits_{i=1}^nd_i\times (n-i+1) di=ai−ai−1an=i=1∑ndipren=i=1∑nai=x=1∑ni=1∑xdi=i=1∑ndi×(n−i+1)
差分维护区间修改
[
l
,
r
]
\large [l,r]
[l,r]
d
l
+
=
x
,
d
r
+
1
−
=
x
\large d_l+=x,d_{r+1}-=x
dl+=x,dr+1−=x
二维
d i , j = a i , j − a i − 1 , j − a i , j − 1 + a i − 1 , j − 1 a i , j = d i , j + d i − 1 , j + d i , j − 1 − d i − 1 , j − 1 = ∑ x = 1 i ∑ y = 1 j d x , y p r e i , j = a i , j + p r e i − 1 , j + p r e i , j − 1 − p r e i − 1 , j − 1 = ∑ x = 1 i ∑ y = 1 j a x , y = ∑ x = 1 i ∑ y = 1 j ∑ k = 1 x ∑ l = 1 y a k , l s u m o f s u b r e c t a n g l e { x 1 ≤ x ≤ x 2 , y 1 ≤ y ≤ y 2 } = p r e x 2 , y 2 − p r e x 1 − 1 , y 2 − p r e x 2 , y 1 − 1 + p r e x 1 − 1 , y 1 − 1 \large d_{i,j}=a_{i,j}-a_{i-1,j}-a_{i,j-1}+a_{i-1,j-1} \\ \large a_{i,j}=d_{i,j}+d_{i-1,j}+d_{i,j-1}-d_{i-1,j-1}=\sum\limits_{x=1}^i\sum\limits_{y=1}^j d_{x,y} \\ \large pre_{i,j}=a_{i,j}+pre_{i-1,j}+pre_{i,j-1}-pre_{i-1,j-1} \\ \large =\sum\limits_{x=1}^i\sum\limits_{y=1}^ja_{x,y}=\sum\limits_{x=1}^i\sum\limits_{y=1}^j\sum\limits_{k=1}^x\sum\limits_{l=1}^ya_{k,l} \\ \large sum\ of\ subrectangle\{x_1\le x\le x_2,y_1\le y\le y_2\} \\ \large = pre_{x_2,y_2}-pre_{x_1-1,y_2}-pre_{x_2,y_1-1}+pre_{x_1-1,y_1-1} di,j=ai,j−ai−1,j−ai,j−1+ai−1,j−1ai,j=di,j+di−1,j+di,j−1−di−1,j−1=x=1∑iy=1∑jdx,yprei,j=ai,j+prei−1,j+prei,j−1−prei−1,j−1=x=1∑iy=1∑jax,y=x=1∑iy=1∑jk=1∑xl=1∑yak,lsum of subrectangle{x1≤x≤x2,y1≤y≤y2}=prex2,y2−prex1−1,y2−prex2,y1−1+prex1−1,y1−1
差分维护子矩形修改，左上角
(
x
1
,
y
1
)
\large (x_1,y_1)
(x1,y1)，右下角
(
x
2
,
y
2
)
\large (x_2,y_2)
(x2,y2)
d
x
1
,
y
1
+
=
w
d
x
2
+
1
,
y
1
−
=
w
d
x
1
,
y
2
+
1
−
=
w
d
x
2
+
1
,
y
2
+
1
+
=
w
\large d_{x_1,y_1}+=w \\ \large d_{x_2+1,y_1}-=w \\ \large d_{x_1,y_2+1}-=w \\ \large d_{x_2+1,y_2+1}+=w \\
dx1,y1+=wdx2+1,y1−=wdx1,y2+1−=wdx2+1,y2+1+=w
BIT
一维
Q1：区间修改，单点求和
B I T BIT BIT维护差分值即可。
Q2：区间修改，区间求和。
考虑下面的等式
p r e n = ∑ i = 1 n d i × ( n − i + 1 ) − ∑ i = 1 n [ ( n + 1 ) d i − i × d i ] \large pre_n=\sum\limits_{i=1}^nd_i\times (n-i+1)-\sum\limits_{i=1}^n [(n+1)d_i-i\times d_i] pren=i=1∑ndi×(n−i+1)−i=1∑n[(n+1)di−i×di]
考虑分成两部分： ( n + 1 ) d i , i d i \large (n+1)d_i,\quad id_i (n+1)di,idi
两个 B I T BIT BIT分别维护 d i \large d_i di， i d i \large id_i idi 即可。
二维
Q1：区间修改，单点求和。
一个二维 B I T BIT BIT维护二维差分数组即可。
Q2：区间修改，区间求和。
考虑下面等式
p r e x , y = ∑ i = 1 x ∑ j = 1 y ∑ k = 1 i ∑ l = 1 j d k , l \large pre_{x,y}=\sum\limits_{i=1}^x \sum\limits_{j=1}^y \sum\limits_{k=1}^i \sum\limits_{l=1}^jd_{k,l} prex,y=i=1∑xj=1∑yk=1∑il=1∑jdk,l
= ∑ i = 1 x ∑ j = 1 y d i , j × ( x − i + 1 ) × ( y − j + 1 ) \large =\sum\limits_{i=1}^x\sum\limits_{j=1}^y d_{i,j}\times (x-i+1)\times (y-j+1) =i=1∑xj=1∑ydi,j×(x−i+1)×(y−j+1)
= ∑ i = 1 x ∑ j = 1 y d i , j ( x + 1 ) ( y + 1 ) − ( y + 1 ) × i d i , j − ( x + 1 ) × j d i , j + i j d i , j \large =\sum\limits_{i=1}^x\sum\limits_{j=1}^y d_{i,j}(x+1)(y+1)-(y+1)\times id_{i,j}-(x+1)\times jd_{i,j}+ijd_{i,j} =i=1∑xj=1∑ydi,j(x+1)(y+1)−(y+1)×idi,j−(x+1)×jdi,j+ijdi,j
因此用 4 4 4个二维 B I T BIT BIT维护 d i , j , i d i , j , j d i , j , i j d i , j \large d_{i,j},id_{i,j},jd_{i,j},ijd_{i,j} di,j,idi,j,jdi,j,ijdi,j 即可。
二维区间修改，区间求和习题
P4514 上帝造题的七分钟
// Problem: P4514 上帝造题的七分钟
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4514
// Memory Limit: 128 MB
// Time Limit: 2000 ms
// Date: 2021-07-24 19:37:56
// --------by Herio--------
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=(1<<11)+1,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define IOS ios::sync_with_stdio(false),cin.tie(0)
void Print(int *a,int n){
for(int i=1;i<n;i++)
printf("%d ",a[i]);
printf("%d\n",a[n]);
}
int n,m;
struct bit{
#define lowbit(x) x&(-x)
#define il inline
int c[N][N];
il void add(int x,int y,int w){
for(int i=x;i<=n;i+=lowbit(i))
for(int j=y;j<=m;j+=lowbit(j))
c[i][j]+=w;
}
il int que(int x,int y){
int s=0;
for(int i=x;i;i-=lowbit(i))
for(int j=y;j;j-=lowbit(j))
s+=c[i][j];
return s;
}
}a,ai,aj,aij;
void add(int x,int y,int w){
a.add(x,y,w);
ai.add(x,y,x*w);
aj.add(x,y,y*w);
aij.add(x,y,x*y*w);
}
void add(int u,int v,int x,int y,int w){
add(u,v,w);
add(u,y+1,-w);
add(x+1,v,-w);
add(x+1,y+1,w);
}
int que(int x,int y){
return a.que(x,y)*(x*y+x+y+1)-ai.que(x,y)*(y+1)-aj.que(x,y)*(x+1)+aij.que(x,y);
}
int que(int u,int v,int x,int y){
return que(x,y)-que(x,v-1)-que(u-1,y)+que(u-1,v-1);
}
int main(){
char ch;
scanf("\n%c%d%d",&ch,&n,&m);
while(~scanf("\n%c",&ch)){
if(ch=='\n') break;
int a,b,x,y,w;
if(ch=='L'){
scanf("%d%d%d%d%d",&a,&b,&x,&y,&w);
add(a,b,x,y,w);
}
else if(ch=='k'){
scanf("%d%d%d%d",&a,&b,&x,&y);
printf("%d\n",que(a,b,x,y));
}
}
return 0;
}