前缀和与差分
一维前缀和
e.g. 给定长度为n的数组arr, 求q次询问中每次arr在[l,r]的区间和
暴力枚举的时间复杂度为O(qn) 容易TLE
使用前缀和可以极大减少运行时间
前缀和数组
定义一个前缀和数组prefix[i]=prefix[i-1]+arr[i]，其中i>0
i=0时sum[0]=arr[0]
则对于数a1,a2,a3,a4,a5….
prefix[1]=a1
prefix[2]=a1+a2
prefix[3]=a1+a2+a3
…
可以看出，prefix[i]为区间[0,i]的和
在求区间的和时，如2-4，就可以使用prefix[4]-prefix[1],通式为prefix[r]-prefix[l-1],
l=0时为prefix[r]
其中，求前缀和的过程成为预处理
板子
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
| #include <iostream>
using namespace std;
const int N = 10000;
int a[N], prefix[10000];
int get_sum(int l , int r){
if (l) return prefix[r]-prefix[l-1];
else return prefix[r];
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
for (int i = 1; i <=n ; i++)
{
cin >> a[i];
}
for (int i = 1; i <= n; i++)
{
prefix[i] = prefix[i-1]+a[i];
}
int q;
cin >> q;
while (q--){
int l, r ;
cin >> l >> r;
cout << get_sum(l,r);
}
return 0;
}
|
二维前缀和
给定一个长n,宽m的矩阵:
求矩阵任意两点间矩形的数字之和
二维前缀和数组
定义一个二维前缀和数组prefix[i][j] =prefix[i-1][j]+prefix[i][j-1]-prefix[i-1][j-1]+a[i][j]，其中i>0
其中，prefix[i][j]为从(0,0)到(i,j)的和
- 当i=0且j=0时，
prefix[0][0]=a[0][0]
- 当i=0且j!=0时，
prefix[0][j]=prefix[0][j-i]+a[0][j]
- 当i!=0且j=0时，
prefix[i][0]=prefix[i-1][0]+a[i][0]
如下图：
%E5%9F%BA%E7%A1%80%E7%AE%97%E6%B3%95/%E5%89%8D%E7%BC%80%E5%92%8C%E4%B8%8E%E5%B7%AE%E5%88%86/%E4%BA%8C%E4%BD%8D%E5%89%8D%E7%BC%80%E5%92%8C.png "二维前缀和")
即prefix[i][j]是由a[i][j],prefix[i-1][j],prefix[i][j-1]组成的，但两块加多了一块prefix[i-1][j-1]，故减去
若要求解某部分矩形，就可以进行以上的逆过程
a[i][j]=prefix[i][j]-prefix[i-1][j]-prefix[i][j-1]+prefix[i-1][j-1]
%E5%9F%BA%E7%A1%80%E7%AE%97%E6%B3%95/%E5%89%8D%E7%BC%80%E5%92%8C%E4%B8%8E%E5%B7%AE%E5%88%86/%E4%BA%8C%E4%BD%8D%E5%89%8D%E7%BC%80%E5%92%8C2.png "二维前缀和2")
从prefix[i][j]开始，求a[i][j]，则可以依次减去prefix[i-1][j],prefix[i][j-1]，但会多减一块prefix[i-1][j-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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include <iostream>
using namespace std;
const int N = 10000;
int n,m;
int a[N][N];
int prefix[N][N];
void pre_sum(){
for (int i = 1;i<=n;i++){
for (int j = 1;j<=m;j++){
prefix[i][j] = prefix[i-1][j]+prefix[i][j-1]-prefix[i-1][j-1]+a[i][j];
}
}
}
int get_sum(int x1, int y1, int x2, int y2){
return prefix[x2][y2]-prefix[x1-1][y2]-prefix[x2][y1-1]+prefix[x1-1][y1-1];
}
int main(){
int x1,y1,x2,y2;
cin >> n >>m;
for (int i = 1; i <=n; i++){
for (int j = 1;j <=m; j++){
cin >> a[i][j];
}
}
cin >> x1 >> y1 >> x2 >> y2;
pre_sum();
cout << get_sum(x1,y1,x2,y2);
return 0;
}
|
一维差分
给定长度为n的数组arr，进行m个操作，使[l,r]区间内的值都加一个value，操作结束后，询问arr
暴力解法：每次遍历数组[l,r]执行加value操作，遍历m次，时间复杂度O(n*m)
例如 arr中有五个数 1 3 7 5 2
对[2,4] +5 [1,3] +2 [0,2] -3
对于下标为2的数分析，7+5+2-3=11. 若不管中间，则相当于7+4=11.
则我们的目的即为让中间的步骤省略，最后只+4.
差分数组
定义一个差分数组d[i]=arr[i]-arr[i-1]
则对d进行前缀和，得到前缀和数组sum，我们可以发现：
差分数组可以通过前缀和得到原数组
即d[i]+=d[i-1]
差分标记
对于一位差分区间修改：[l,r]+valued[l]+value, d[r+1]-value
对于以上arr 对应差分数组d为1 2 4 -2 -3
第一次操作等价于d[2]+5 结果为1 2 9 -2 -3
第二次等价于d[1]+2,d[4]-2 结果为1 4 9 -2 -5
第三次：-2 4 9 1 -5
进行前缀和得到sum -2 2 11 12 7
注意：
- 把标记后的差分数组进行一次前缀和操作
- 每进行m次操作后都要进行一次前缀和
- 即适用于多次操作单次询问（单次操作单次询问不适用）
原理：
差分数组中，标记位加了一个数，还原成原数组的时候，后面的数都会累加，然后再r+1位在减去这个数停止累加
最终实现的效果为：sum[l,r]+value,
sum[r+1,n-1] +value - value
如：对于差分数组d 0 1 0 0 0，进行一次前缀和后其sum为 0 1 1 1
1，即标记位加的数会作用与该标记之后每一位，即d[i]+value sum[i,n-1]+value
若想在某位置停止累加，在该位置+1处减掉value即可，如 d 0 1 0 0
-1，前缀和后sum为 0 1 1 1 0，加一减一抵消为0，即d[r+1]-value
sum[r+1,n-1]-value
板子
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
36
37
38
39
40
41
42
43
44
45
| #include <iostream>
using namespace std;
int main(){
int a[10000]={0}, diff[10000]={0}, prefix[10000]={0};
int n;
cin >> n;
for (int i = 1; i <=n ; i++)
{
cin >> a[i];
}
for (int i = 1; i <= n; i++)
{
diff[i] = a[i]-a[i-1];
}
int m;
cin >> m;
while(m--){
int l, r, x;
cin >> l>> r>> x;
diff[l]+=x, diff[r+1]-=x;
}
for (int i = 1; i <=n; i++)
{
a[i] = a[i-1] +diff[i];
}
for (int i = 1; i <= n; i++)
{
prefix[i] = prefix[i-1]+a[i];
}
int q;
cin >> q;
while (q--){
int l, r ;
cin >> l >> r;
cout << prefix[r]-prefix[l-1];
}
return 0;
}
|
二维差分
给定长n,宽m的矩阵，从(xi,yi)到(xj,yj)执行m次操作，使两点间矩形中的值都加一个value，操作结束后，询问矩阵
大体思路与一维差分差不多
差分矩阵
定义一个差分矩阵：d[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]
或者可以将差分矩阵中的元素一个个插入：
即若原矩阵(x,y)处值为value，则相当于从左上角(x,y)
到右下角(x,y)都加value,也可以使用差分标记实现
差分标记
对于二位差分区间修改：[(xi,yi),(xj,yj)]+valued[xi][yi]+value, d[xj+1][yi]-value, d[xi][yj+1]-value, d[xj+1][yj+1]+value
原理如图：
%E5%9F%BA%E7%A1%80%E7%AE%97%E6%B3%95/%E5%89%8D%E7%BC%80%E5%92%8C%E4%B8%8E%E5%B7%AE%E5%88%86/%E4%BA%8C%E4%BD%8D%E5%B7%AE%E5%88%86%E5%8F%AF%E8%A7%86%E5%8C%96.png "二位差分可视化")
板子
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
36
37
38
39
40
41
42
43
44
45
46
| #include <iostream>
using namespace std;
const int N = 10000;
int n,m,cnt=0;
int a[N][N];
int prefix[N][N];
int d[N][N];
void add(int x1, int y1, int x2, int y2,int value){
d[x1][y1]+=value;
d[x2+1][y1]-=value;
d[x1][y2+1]-=value;
d[x2+1][y2+1]+=value;
}
int main(){
cin >> n >>m >> cnt;
for (int i = 1; i <=n; i++){
for (int j = 1;j <=m; j++){
cin >> a[i][j];
add(i,j,i,j,a[i][j]);
}
}
for (int i = 1; i <=cnt;i++){
int x1,y1,x2,y2,value;
cin >> x1 >> y1 >> x2 >> y2>>value;
add(x1,y1,x2,y2,value);
}
for (int i = 1 ;i <=n;i++){
for (int j = 1;j <=m;j++){
a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + d[i][j];
}
}
for (int i = 1;i <= n; i++){
for (int j = 1; j <= m; j++){
cout << a[i][j] << ' ';
}
cout << endl;
}
return 0;
}
|
