归档157

791 字

4 分钟

差分

2025-10-03

数据结构与算法

差分#

差分可以看作前缀和的反向操作。前缀和擅长快速查询区间和，差分擅长快速做区间修改。

如果题目经常出现：

1
把区间 [l, r] 中每个数都加上 c

那么差分就是很适合的工具。

1、一维差分的思想#

假设原数组是 a，差分数组是 b：

1
b[1] = a[1]
2
b[2] = a[2] - a[1]
3
b[3] = a[3] - a[2]
4
...

那么对 b 求前缀和，就能还原 a：

1
a[i] = b[1] + b[2] + ... + b[i]

2、为什么区间加能变成 O(1)#

如果想让 [l, r] 都加上 c，只需要：

1
b[l] += c
2
b[r + 1] -= c

原因是：

从 l 开始，前缀和都会多加 c。
到 r + 1 时，再减掉 c，让后面的数恢复原样。

3、一维差分模板#

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
const int N = 100010;
5

6
int n, m;
7
int a[N], b[N];
8

9
void insert(int l, int r, int c) {
10
    b[l] += c;
11
    b[r + 1] -= c;
12
}
13

14
int main() {
15
    scanf("%d%d", &n, &m);
16

17
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
18

19
    for (int i = 1; i <= n; i++) {
20
        insert(i, i, a[i]);
21
    }
22

23
    while (m--) {
24
        int l, r, c;
25
        scanf("%d%d%d", &l, &r, &c);
26
        insert(l, r, c);
27
    }
28

29
    for (int i = 1; i <= n; i++) {
30
        b[i] += b[i - 1];
31
        printf("%d ", b[i]);
32
    }
33

34
    return 0;
35
}

4、二维差分解决什么问题#

二维差分对应的是矩阵里的子矩形修改：

1
把左上角 (x1, y1) 到右下角 (x2, y2) 的所有元素都加上 c

如果直接遍历子矩形，复杂度可能很高。二维差分可以把一次矩形修改变成 O(1)。

5、二维差分公式#

对子矩形加 c：

1
b[x1][y1] += c
2
b[x2 + 1][y1] -= c
3
b[x1][y2 + 1] -= c
4
b[x2 + 1][y2 + 1] += c

最后对差分矩阵做二维前缀和，就能得到修改后的原矩阵。

6、二维差分模板#

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
const int N = 1010;
5

6
int n, m, q;
7
int a[N][N], b[N][N];
8

9
void insert(int x1, int y1, int x2, int y2, int c) {
10
    b[x1][y1] += c;
11
    b[x2 + 1][y1] -= c;
12
    b[x1][y2 + 1] -= c;
13
    b[x2 + 1][y2 + 1] += c;
14
}
15

16
int main() {
17
    scanf("%d%d%d", &n, &m, &q);
18

19
    for (int i = 1; i <= n; i++) {
20
        for (int j = 1; j <= m; j++) {
21
            scanf("%d", &a[i][j]);
22
            insert(i, j, i, j, a[i][j]);
23
        }
24
    }
25

26
    while (q--) {
27
        int x1, y1, x2, y2, c;
28
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
29
        insert(x1, y1, x2, y2, c);
30
    }
31

32
    for (int i = 1; i <= n; i++) {
33
        for (int j = 1; j <= m; j++) {
34
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
35
            printf("%d ", b[i][j]);
36
        }
37
        printf("\n");
38
    }
39

40
    return 0;
41
}

7、差分和前缀和的关系#

可以这样理解：

1
差分数组 --做前缀和--> 原数组
2
原数组 --相邻项相减--> 差分数组

所以差分最后一定要“还原”，也就是做一次前缀和。

8、容易写错的地方#

（1）一维区间右端要写 `r + 1`#

1
b[r + 1] -= c;

这是让影响在 r 后面停止。

（2）二维右下角是 `x2 + 1, y2 + 1`#

1
b[x2 + 1][y2 + 1] += c;

不要写成 b[x2][y2] += c。

（3）还原二维矩阵时列数用 `m`#

1
for (int j = 1; j <= m; j++)

不要把列循环写成 j <= n。

总结#

差分适合“多次区间修改，最后一次性输出结果”的问题。

1
一维：b[l] += c, b[r + 1] -= c
2
二维：四个角做加减

文章分享

如果这篇文章对你有帮助，欢迎分享给更多人！

差分

https://blog.tjcheng.cn/posts/migrated/old-78/

作者

TengJinCheng

发布于

2025-10-03

许可协议

CC BY-NC-SA 4.0

conda下载路径的修改

前缀和

音乐

音乐

差分#

1、一维差分的思想#

2、为什么区间加能变成 O(1)#

3、一维差分模板#

4、二维差分解决什么问题#

5、二维差分公式#

6、二维差分模板#

7、差分和前缀和的关系#

8、容易写错的地方#

（1）一维区间右端要写 `r + 1`#

（2）二维右下角是 `x2 + 1, y2 + 1`#

（3）还原二维矩阵时列数用 `m`#

总结#

文章分享

音乐

文章目录

音乐

音乐

差分

差分#

1、一维差分的思想#

2、为什么区间加能变成 O(1)#

3、一维差分模板#

4、二维差分解决什么问题#

5、二维差分公式#

6、二维差分模板#

7、差分和前缀和的关系#

8、容易写错的地方#

（1）一维区间右端要写 r + 1#

（2）二维右下角是 x2 + 1, y2 + 1#

（3）还原二维矩阵时列数用 m#

总结#

文章分享

音乐

文章目录

（1）一维区间右端要写 `r + 1`#

（2）二维右下角是 `x2 + 1, y2 + 1`#

（3）还原二维矩阵时列数用 `m`#