我的算法书 - 差分

一句话算法

差分把“区间整体修改”变成“边界两个点修改”，最后再用前缀和还原原数组。

问题模型

给定一个数组 $a_1,a_2,\dots,a_n$ ，有多次操作：

将区间 $[l,r]$ 中的每个数都加上 $v$ 。

所有修改完成后，输出最终数组。

如果每次都逐个修改 $a_l,a_{l+1},\dots,a_r$ ，单次操作最坏需要 $O(n)$ 。差分数组可以把一次区间修改降为 $O(1)$ ，最后用一次 $O(n)$ 的前缀和还原。

“适用边界”

普通差分适合“多次区间修改，最后一次性查询最终数组”的离线场景。

如果修改和查询交替出现，通常需要树状数组或线段树维护差分。

核心直觉

前缀和记录“从开头到当前位置累加了多少”，差分记录“当前位置相对前一个位置变化了多少”。

定义：

d_i=a_i-a_{i-1},\quad a_0=0

于是：

a_i=d_1+d_2+\cdots+d_i

也就是说，原数组 $a$ 是差分数组 $d$ 的前缀和。

现在如果要让 $[l,r]$ 每个数都增加 $v$ ：

从 $l$ 开始，后面的前缀和都应该多 $v$ ，所以 d[l] += v。
从 $r+1$ 开始，这个增量应该停止，所以 d[r + 1] -= v。

这样一来， $l$ 到 $r$ 会多加 $v$ ， $r+1$ 之后又被抵消，区间外不受影响。

算法步骤

一维差分

建立差分数组：
$d_i=a_i-a_{i-1}$

对每个区间修改

[l,r]

加

v

：

cpp

        1
2

        d[l] += v;
d[r + 1] -= v;

所有修改完成后，用前缀和还原：
$a_i=a_{i-1}+d_i$

二维差分

二维差分处理子矩形修改。若要让矩形左上角 $(x_1,y_1)$ 、右下角 $(x_2,y_2)$ 内全部加 $v$ ，修改四个角：

cpp

        1
2
3
4

        d[x1][y1] += v;
d[x2 + 1][y1] -= v;
d[x1][y2 + 1] -= v;
d[x2 + 1][y2 + 1] += v;

还原时做二维前缀和：

a_{i,j}=a_{i-1,j}+a_{i,j-1}-a_{i-1,j-1}+d_{i,j}

算法证明

一维差分为什么只改两个点

只考虑一次操作：区间 $[l,r]$ 加 $v$ 。

左边界启动增量
$d_l \leftarrow d_l+v$
对差分做前缀和时，从 $l$ 开始，每个位置都会多累加到这个 $v$ 。
右边界后停止增量
$d_{r+1} \leftarrow d_{r+1}-v$
从 $r+1$ 开始，前面多出来的 $v$ 被抵消。
分段看效果
- $i<l$ ：没有经过 +v，不变。
- $l \le i \le r$ ：经过 +v，还没经过 -v，多 $v$ 。
- $i>r$ ：既经过 +v 又经过 -v，抵消后不变。

所以这两个点的修改，等价于原数组区间 $[l,r]$ 整体加 $v$ 。

二维差分为什么改四个点

二维里，一个差分点 $(x,y)$ 会影响它右下方所有位置。

要让矩形 $[x_1,x_2]\times[y_1,y_2]$ 增加 $v$ ：

d[x1][y1] += v：先让目标矩形及其右下方全部增加 $v$ 。
d[x2 + 1][y1] -= v：切掉目标矩形下方多出的部分。
d[x1][y2 + 1] -= v：切掉目标矩形右方多出的部分。
d[x2 + 1][y2 + 1] += v：右下角区域被前两次切掉操作重复扣了一次，需要补回。

这就是二维版本的容斥。

复杂度分析

一维差分：

建差分： $O(n)$ 。
单次区间修改： $O(1)$ 。
最后还原： $O(n)$ 。
空间复杂度： $O(n)$ 。

二维差分：

单次子矩形修改： $O(1)$ 。
最后还原： $O(nm)$ 。
空间复杂度： $O(nm)$ 。

代码实现

一维差分

cpp

        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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

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

using ll = long long;

struct DifferenceArray {
    int n = 0;
    vector<ll> diff;

    DifferenceArray() = default;

    explicit DifferenceArray(const vector<ll>& a) {
        init(a);
    }

    // a 使用 0 下标存储；diff 使用 1 下标，方便处理区间 [l, r]。
    void init(const vector<ll>& a) {
        n = (int)a.size();
        diff.assign(n + 2, 0);
        for (int i = 1; i <= n; i++) {
            diff[i] = a[i - 1] - (i == 1 ? 0 : a[i - 2]);
        }
    }

    // 对原数组的 1 下标闭区间 [l, r] 全部加 v。
    void add(int l, int r, ll v) {
        diff[l] += v;
        diff[r + 1] -= v;
    }

    // 将差分数组还原成 1 下标原数组。
    vector<ll> restore() const {
        vector<ll> a(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            a[i] = a[i - 1] + diff[i];
        }
        return a;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    DifferenceArray da(a);

    while (m--) {
        int l, r;
        ll v;
        cin >> l >> r >> v;
        da.add(l, r, v);
    }

    vector<ll> ans = da.restore();
    for (int i = 1; i <= n; i++) {
        if (i > 1) cout << ' ';
        cout << ans[i];
    }
    cout << '\n';

    return 0;
}

二维差分

cpp

        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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

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

using ll = long long;

struct Difference2D {
    int n = 0, m = 0;
    vector<vector<ll>> diff;

    Difference2D() = default;

    Difference2D(int n_, int m_) {
        init(n_, m_);
    }

    void init(int n_, int m_) {
        n = n_;
        m = m_;
        diff.assign(n + 2, vector<ll>(m + 2, 0));
    }

    // 对原矩阵的子矩形 [(x1, y1), (x2, y2)] 全部加 v，坐标从 1 开始。
    void add(int x1, int y1, int x2, int y2, ll v) {
        diff[x1][y1] += v;
        diff[x2 + 1][y1] -= v;
        diff[x1][y2 + 1] -= v;
        diff[x2 + 1][y2 + 1] += v;
    }

    vector<vector<ll>> restore() const {
        vector<vector<ll>> a(n + 1, vector<ll>(m + 1, 0));
        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] + diff[i][j];
            }
        }
        return a;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    cin >> n >> m >> q;

    Difference2D d(n, m);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ll x;
            cin >> x;
            d.add(i, j, i, j, x);
        }
    }

    while (q--) {
        int x1, y1, x2, y2;
        ll v;
        cin >> x1 >> y1 >> x2 >> y2 >> v;
        d.add(x1, y1, x2, y2, v);
    }

    vector<vector<ll>> ans = d.restore();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (j > 1) cout << ' ';
            cout << ans[i][j];
        }
        cout << '\n';
    }

    return 0;
}

测试用例

一维差分输入：

6 2
3 5 1 7 8 4
2 4 2
3 6 -1

输出：

3 7 2 8 7 3

解释：

第一次修改后：3 7 3 9 8 4
第二次修改后：3 7 2 8 7 3

二维差分可以用下面的输入测试：

输出：

3 3 0 0
3 3 5 5
0 0 5 5

应用分类详解

差分的本质是：把一段连续影响拆成“开始”和“结束”两个边界事件。看到“批量区间加减，最后问结果”，就应该先想到差分。

一、区间修改，最后查询最终数组

典型模式： 多次给连续区间加减，所有操作结束后输出每个位置最终值。

识别信号： 题面出现“区间加”“所有操作后”“最终数组”“每个位置的值”。

核心建模： 每次操作只改差分数组的两个边界，最后做一次前缀和。

应用场景	经典题目	核心思路
区间加模板	luogu-P2367	每次修改两个端点，最后还原数组
叠加覆盖统计	HDU 1556 Color the ball	每个染色区间转成差分边界

二、判断资源是否被区间操作压垮

典型模式： 多个区间需求叠加，问某些位置是否超过限制。

识别信号： 题面出现“每天/每段资源消耗”“区间订单”“是否超过容量”。

核心建模： 用差分统计每个位置承受的总增量，再和限制比较。

应用场景	经典题目	核心思路
资源区间消耗	luogu-P1083	检查前若干订单是否导致某天资源为负
区间高度约束	POJ 3263 Tallest Cow	约束影响一段连续位置，用差分叠加

三、二维矩形批量修改

典型模式： 网格、地图、矩阵里，多次对子矩形整体加减。

识别信号： 题面出现“矩形区域”“左上角右下角”“地毯覆盖”“二维平面增量”。

核心建模： 一次矩形修改转成二维差分四个角的修改，最后二维前缀和还原。

应用场景	经典题目	核心思路
地毯覆盖	luogu-P3397	每张地毯是一个矩形加一
二维热力图叠加	矩阵覆盖类题目	每个覆盖矩形只改四个边界点

四、差分作为其他数据结构的基础

典型模式： 区间修改和查询交替出现，普通离线差分不够用。

识别信号： 题面同时出现“修改区间”和“查询某点/某段”，并且操作在线交替。

核心建模： 维护差分数组。若需要在线单点查询，可用树状数组维护差分前缀和；若需要更复杂区间查询，用线段树。

应用场景	经典题目	核心思路
区间修改，单点查询	luogu-P3368	树状数组维护差分数组
树上路径修改	树上差分题	路径影响转为若干关键点增减

经典例题

1. luogu-P2367

一维差分模板题。多次区间加减，最后输出每个学生的成绩。每次修改两个差分边界，最后还原即可。

2. luogu-P3397

二维差分模板题。每张地毯覆盖一个子矩形，等价于对子矩形整体加 $1$ 。用四角修改记录所有地毯，最后还原每个格子的覆盖次数。

3. luogu-P1083

借教室问题可以用差分作为检查函数：给定前 $k$ 个订单，差分叠加每一天被借走的教室数，再判断是否超过容量。外层通常配合二分找到第一份不满足的订单。

4. luogu-P4552

这类题会直接考察差分数组的变化量。把原数组变成目标形态时，观察相邻差值如何变化，比直接操作原数组更清晰。

参考

旧版文章：Rbook_ejs_old/book/base/differential/index.md
当前草稿：book/pages/base/差分/二维差分.md