参考博客

一维差分  二维差分

一维差分

一维差分在前面讲解的树状数组的区间修改与查询中有具体应用

定义

差分是一种前缀和相对的策略。对于一个数列 ai ，我们维护的数据是“相邻两个数的差”

我们称数列 pi 就是数列 ai 的差分数列

应用

维护序列并查询某个数

譬如使 [l,r] 上的每个数加上 k ，那么维护序列 p 修改操作是：

查询 a[i] 的操作就是做一遍前缀和：

维护序列并查询某个区间的和

维护序列的操作和上述相同，借助上述求某个值的方法可以发现如下规律：

所以我们可以在每次维护 p[i] 的同时，在维护一个序列 q[i]=(i-1)*p[i] ，如此查询区间和的时候只用将 p[] 的前缀和减去 q[] 的前缀和即可：

模板

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
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;

int n, m;
int a[100005], p[100005], q[100005];

void input(int i, int x){
	a[i] = x;
	p[i] = a[i] - a[i - 1];
	q[i] = (i - 1) * p[i];
}

void change(int l, int r, int c){
	p[l] += c, p[r + 1] -= c;
	q[l] += (l - 1) * c, q[r + 1] -= r * c;
}

int query(int pos){
	int ans = 0;
	for (int i = 1; i <= pos; ++i){
		ans += p[i];
	}
	return ans;
}

int getsum(int pos){
	int ans = 0;
	for(int i = 1; i <= pos; ++i){
		ans += pos*p[i] - q[i];
	}
	return ans;
}

signed main()
{
	ios::sync_with_stdio(false),cin.tie(0);
	while(cin >> n >> m){
		for(int i = 1; i <= n; ++i){ //必须从下标1开始存，因为差分要用到下标0的位置
			int x;
			cin >> x;
			input(i, x);//存入时初始化相应的p[]和q[]
		}
		while(m--){
			int l, r, c;
			cin >> l >> r >> c;
			change(l, r, c);
		}
		//输出a[i]和区间[1,i]的和
		for(int i = 1; i <= n; ++i){
			cout << query(i) << ' ' << getsum(i) << endl;
		}
		cout << endl;
	}
	return 0;
}

二维差分

定义

二维差分就是一维差分的拓展，其原理没有任何变化

根据二维前缀和表示的是右上角矩形的和，由于差分只涉及前面相邻的数（由一维可以推出），并且由前面范围的数相加得到这个位置的数。那么类比二维前缀和和一维差分，可以简单推测出二维差分的公式：

即当前点的差分 p[i][j] 是 a[i][j] 的与左边和上边相邻点的差值、与左上角相邻点的加和的总和

应用

由上述定义逆推就可以得到查询某个点的方法：

二维差分的维护涉及重叠问题，如果我们要在左上角是 (x1,y1)，右下角是 (x2,y2) 的矩形区间每个值都 +a，如下图所示

在我们要的区间开始位置（x1,y1）处 +c，根据前缀和的性质，那么它影响的就是整个黄色部分，多影响了两个蓝色部分，所以在两个蓝色部分 -c 消除 +c 的影响，而两个蓝色部分重叠的绿色部分多了个 -c 的影响，所以绿色部分 +c 消除影响。所以对应的计算方法如下：

1
2
3
4
5
6
void change(int x1, int y1, int c, int x2, int y2){
    p[x1][y1] += c;
    p[x1][y2+1] -=c;
    p[x2+1][y1] -=c;
    p[x2+1][y2+1] += c;
}

如果将某个 a*b 的矩阵以左上角 (i,j) 为出发点的所有点加上 c 就可以表示为：

1
2
3
4
5
6
7
void change(int x, int y, int k, int a, int b){ //(x,y)为左上角长a,宽为b的矩阵值+=k
    int dx = x + a, dy = y + b;
    p[x][y] += k;
    p[dx][y] -= k;
    p[x][dy] -= k;
    p[dx][dy] += k;
}

模板

模板题1：输入一个 n 行 m 列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 x1，y1，x2，y2，c，其中 (x1, y1) 和 (x2, y2) 表示一个子矩阵的左上角坐标和右下角坐标。每个操作都要将选中的子矩阵中的每个元素的值加上 c。请你将进行完所有操作后的矩阵输出。

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+5;

int a[maxn][maxn];
int p[maxn][maxn];

void change(int x1, int y1, int c, int x2, int y2){
    p[x1][y1] += c;
    p[x1][y2+1] -=c;
    p[x2+1][y1] -=c;
    p[x2+1][y2+1] += c;
}

int main() {
    int n,m,q;
    scanf("%d%d%d", &n, &m, &q);
    for(int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            scanf("%d", &a[i][j]);
            p[i][j] = a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];
        }
    }
    for(int i=0; i<q; i++) {
        int x1, y1, x2, y2, c;
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
        change(x1, y1, c, x2, y2);
    }
    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];
            printf("%d ", p[i][j]);
        }
        printf("\n");
    }
    return 0;
}

模板题2：2020ICPC小米邀请赛网络赛第一场J题