acwing算法基础之基础算法--差分算法

1 知识点

已知原数组$a_1,a_2,\cdots ,a_n$
获得其差分数组$b_1,b_2,\cdots ,b_n$，
$b_1=a_1$
$b_2=a_2-a_1$
$b_i=a_i-a_{i-1}$

此时，数组a是数组b的前缀和数组。

作用：快速处理多个如下这类操作，
对原数组a中的[l,r]区间的数都加上val。
此操作等价于$b_l+=val,b_{r+1}-=val$。

差分并不需要构造差分数组$b$。只需要利用上述性质，在区间[i,i]加上$a_i$即可。

二维情况下，对$(x_1,y_1),(x_2,y_2)$表示的矩阵加上val，等价于
$d[x_1][y_1]+=c$
$d[x_1][y_2+1]-=c$
$d[x_2+1][y1]-=c$
$d[x_2+1][y_2+1]+=c$

初始化，取$(x_1,y_1)$为$(i,j)$，$(x_2,y_2)$为$(i,j)$。

2 模板

//一维情况
//原数组nums，第0位没有含义，从第1位开始存储
int n = nums.size();
vector<int> d(n+10,0);
for (int i = 1; i <= n; ++i) {
	d[i] += nums[i];
	d[i+1] -= nums[i];
}

//在原数组的[l,r]区间中加上c，注意l和r都是从1开始编号的
d[l] += c;
d[r+1] -= c;

//多次操作之后的原数组如下所示
for (int i = 1; i <= n; ++i) {
	d[i] += d[i-1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

//二维情况
//原数组a
//差分数组d
void insert(vector<vector<int>> &d, int x1, int y1, int x2, int y2, int c) {
    d[x1][y1] += c;
    d[x1][y2+1] -= c;
    d[x2+1][y1] -= c;
    d[x2+1][y2+1] += c;
    return;
}

int n = a.size(), m = a[0].size();
vector<vector<int>> d(n+10,vector<int>(m+10,0));
for (int i = 1; i <= n; ++i) {
	for (int j = 1; j <= m; ++j) {
		insert(d, i, j, i, j, a[i][j]);
	}
}

//子矩阵(x1,y1) (x2,y2)加上c
insert(d, x1, y1, x2, y2, c);

//输出最终数组a
//相当于求矩阵的前缀和
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] + b[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
28
29