1.前缀和与差分

1.prefix 前缀和数组

p[i] = p[i-1] + a[i];

优点：便于数组查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//https://www.starrycoding.com/problem/7
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
const int N = 1e5+9;
ll a[N],p[N];

int main(){
   ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
   int T;cin >> T;
   while(T--){
   	ll n,q;cin >> n >> q;
   	for(int i = 1;i <= n;i++){
   		cin >> a[i];
   	}
   	for(int i = 1;i <= n;i++){
   		p[i] = p[i-1] + a[i];
   	}
   	while(q--){
   		ll l,r;cin >> l >> r;
   		cout << p[r] - p[l-1] << '\n';		
   	}
   }
}

2.diff 差分数组

d[i] = a[i] - a[i-1];

优点：便于数组修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//https://www.starrycoding.com/problem/8
#include <bits/stdc++.h>
using namespace std;
using ll =long long ;
const int N = 1e5+9;
ll a[N],c[N],d[N];

int main(){
   ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
   ll n,p,q;cin >> n >> p >> q;
   for(int i = 1;i <= n;i++)cin >> a[i];
   for(int i = 1;i <= n;i++)d[i] = a[i] - a[i-1];
   while(p--){
   	ll l,r,x;cin >> l >> r >> x;
   	d[l] += x;d[r+1] -= x;
   }
   for(int i = 1;i <= n;i++)a[i] = a[i - 1] + d[i];
   for(int i = 1;i <= n;i++)c[i] = c[i - 1] + a[i];
   while(q--){
   	ll l,r;cin >> l >> r;
   	cout << c[r] - c[l-1] << '\n';
   }
}

3.二位前缀和

p[i][j] = p[i-1][j] + p[i][j-1] - p[i-1][j-1] + a[i][j];

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
//https://www.starrycoding.com/problem/15
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3+9;
using ll = long long;
ll  a[N][N],p[N][N];

int main(){
   ios::sync_with_stdio(0),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];

   
   for(int i = 1;i <= n;++i)
   	for(int j = 1;j <= m;++j)
   		p[i][j] = p[i-1][j] + p[i][j-1] - p[i-1][j-1] + a[i][j];
   	
   while(q--){
   	int res = 0;
   	int x1,y1,x2,y2;cin >> x1 >> y1 >> x2 >> y2;
   	res = p[x2][y2] - p[x1-1][y2] - p[x2][y1-1] + p[x1-1][y1-1];
   	cout << res << '\n';
   }
}

4.二维差分

1.差分求法

d[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]

以上这个求法，是将原式作为所求差分的前缀和。

2.标准求法

d[i][j] += a[i][j];

d[i + 1][j] -= a[i][j];

d[i][j + 1] -= a[i][j];

d[i + 1][j + 1] += a[i][j];

两种求法一样，可以互相推导

eg：d[i + 1][j] -= a[i][j]; = d[i][j] -= a[i-1][j]`

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
//https://www.starrycoding.com/problem/50

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1e3+10;
ll a[N][N], d[N][N];

int main(){
   ios::sync_with_stdio(0),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];
   		d[i][j] += a[i][j];
   		d[i + 1][j] -= a[i][j];
   		d[i][j + 1] -= a[i][j];
   		d[i + 1][j + 1] += a[i][j];
   	}
   }
   while (q--)
   {
   	int x1, x2, y1, y2, c;
   	cin >> x1 >> y1 >> x2 >> y2 >> c;
   	d[x1][y1] += c;
   	d[x1][y2 + 1] -= c;
   	d[x2 + 1][y1] -= c;
   	d[x2 + 1][y2 + 1] += c;
   }
   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];
   		cout << a[i][j] << ' ';
   	}
   	cout << '\n';
   }
   return 0;
}