对于一维数组a和数组b
a[i]=b[1]+b[2]+…+b[i];
b[1]=a[1]
b[2]=a[2]-a[1]
··· ···
b[n]=a[n]-a[n-1]
称数组a是数组b的前缀和 数组b是数组a的差分
若将一维数组a的[l,r]区间加上c 且时间复杂度为O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| void insert(int l,int r,int c){
b[l]+=c;
b[r+1]-=c;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int m,n;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
insert(i,i,a[i]);
}
while(m--){
int l,r,c;
cin>>l>>r>>c;
insert(l,r,c);
}
for(int i=1;i<=n;i++){
b[i]=b[i]+b[i-1];
cout<<b[i]<<" ";
}
|
对于二维数组a和数组b
a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];
b[1][1]=a[1][1]-a[1][0]-a[0][1]+a[0][0]
b[2][2]=a[2][2]-a[2][1]-a[1][2]+a[1][1]
··· ···
b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]
称数组a是数组b的前缀和 数组b是数组a的差分
若将二维数组a的[(x1,y1),(x2,y2)]子矩阵加上c 且时间复杂度为O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| void insert(int x1,int y1,int x2,int y2,int c){//这样变化后只有含有加上c的子矩阵元素的前缀和才会改变
b[x1][y1]+=c;
b[x1][y2+1]-=c;
b[x2+1][y1]-=c;
b[x2+1][y2+1]+=c;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,m,q;
cin>>n>>m>>q;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
insert(i,j,i,j,a[i][j]);
}
}
while(q--){
int x1,y1,x2,y2,c;
cin>>x1>>y1>>x2>>y2>>c;
insert(x1,y1,x2,y2,c);//b[x1][y1]和b[x2+1][y2+1]符号为正 b[x1][y2+1]和b[x2+1][y1]符号为负
}
//将数组b化为数组b的前缀和 并输出
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+b[i][j];
cout<<b[i][j]<<" ";
}
cout<<endl;
}
|