差分
作用：快速进行区间修改
给定数列$a$,构造数列$b$使得 $a_k=\sum_{\substack{1\le i\le k }} b_i$,则$b$是$a$的差分数组，$a$是$b$的前缀和数组，前缀和与差分互为逆运算
$b[i]=a[i]-a[i-1]$
此时，若需要把$[l,r]$的数加上$x$,则$a_l$到$a_l$都会加上$x$,此时$b[l]=a[l]-a[l-1]$增大了$x$,$b[r+1]=a[r+1]-a[r]$减小了$x$，所以$b[l]+=x,b[r+1]-=x$
修改后，求前缀和即可得到原数组修改后的结果
例：给一个$n$项数列，共$p$次修改，每次把$[l,r]$之间的数加上$x$,求修改后数列的最小值
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
| #include<bits/stdc++.h>
using namespace std;
const int N=5e6+5;
int n,p;
int a[N],b[N];
int ans=1e9;
int main(){
cin >> n >> p;
for(int i=1;i<=n;i++){
cin >> a[i];
b[i]=a[i]-a[i-1];
}
for(int i=1;i<=p;i++){
int l,r,x;
cin >> l >> r >> x;
b[l]+=x,b[r+1]-=x;
}
for(int i=1;i<=n;i++){
a[i]=a[i-1]+b[i];
ans=min(ans,a[i]);
}
cout << ans;
return 0;
}
|
二维差分
若$b[x][y]$加上$k$,则从点$(x,y)$到$(n,n)$均加上了$k$,所以要给左上点$(x_1,y_1)$,右下点$(x_2,y_2)$的矩阵加上$k$,则$b[x_1][y_1]+=k,b[x_2+1][y_1]-=k,b[x_1][y_2+1]-=k,b[x_2+1][y_2+1]+=k$
最后求前缀和数组即可
例：有一个$n*n$的矩阵，$m$次修改，每次修改把$(x_1,y_1)$到$(x_2,y_2)$的矩阵加$1$,最后求修改后的矩阵
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
| #include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m;
int b[N][N];
void change(int x_1,int y_1,int x_2,int y_2,int k){
b[x_1][y_1]+=k;
b[x_2+1][y_1]-=k;
b[x_1][y_2+1]-=k;
b[x_2+1][y_2+1]+=k;
}
int main(){
cin >> n >> m;
for(int i=1;i<=m;i++){
int a,b,c,d;
cin >> a >> b >> c >> d;
change(a,b,c,d,1);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
cout << b[i][j] << ' ';
}
cout << endl;
}
}
|