前缀和的逆运算——差分数组：区间修改高效算法详解

先聊一个老生常谈的话题：很多人刷题刷到“差分”这个知识点时，第一反应是“又是一个看起来很数学的东西”，然后容易被名字劝退。但实际接触下来你会发现，差分的核心思想只用一个生活场景就能讲清楚——记录相邻两天的体重变化量，一天天累加回去，就能知道每一天的体重。就这么简单。

在算法竞赛里，差分一般指差分数组，它是前缀和的逆运算，专门用来高效处理“区间批量修改”这一类问题。比如说，有一个长度为10万的数组，你要把其中第3到第7个位置全部加上一个数，如果用暴力循环做，一次操作就要遍历5个位置，来10万次操作就是50亿次循环，直接超时。而差分数组可以让每次区间修改只修改两个位置，把所有操作累积完之后，再统一做一次前缀和恢复。这个优化幅度是非常可观的。

这篇文章我会从一维差分讲到二维差分，再总结几类“一看到题目特征就该想到差分”的基础题型，最后分享一些我实际写代码时踩过的坑。适合刚开始学数据结构的同学，也适合准备算法面试和比赛、想把基础打扎实的读者。

1. 差分到底在解决什么问题

1.1 从一个最常见的场景说起

有这样一个需求：给你一个长度为 n 的数组，初始全为 0，接下来有 m 次操作，每次操作给出区间 [l, r] 和一个数值 v，要求把数组中下标从 l 到 r 的所有元素都加上 v。所有操作完成后，输出整个数组。

这是一个非常经典的“区间修改 + 点查询”问题。最暴力的做法就是按题意模拟，每次都在循环里把 l 到 r 的每个位置重新赋值一遍。仔细算一下复杂度：单次操作最坏要遍历整个数组，时间复杂度是 O(n)，m 次操作总复杂度是 O(n×m)。当 n 和 m 都是 10^5 级别时，肯定超时。

差分的思路是把“对一段连续区域的修改”转换成“对两个端点的标记”。你可以把数组想象成一排接水的水槽，差分数组里的每个值代表这个水槽位置的一个水流开关。想在区间 [l, r] 上加水，就在 l 处打开水龙头，在 r+1 处放一个停水挡板。最后把水流从头到尾累积一遍，每个水槽里接到的水量就是最终值。

1.2 前缀和与差分：一对神奇逆运算

要理解差分，最好先理解它和前缀和的关系。

前缀和数组 s 的定义是：s[i] = a[1] + a[2] + ... + a[i]。也就是说，s[i] 是原数组前 i 项的和。

差分数组 d 的定义是：d[i] = a[i] - a[i-1]（规定 a[0] = 0）。也就是相邻两项之间的差值。

这两个操作是互逆的：对差分数组做前缀和，能得到原数组；对原数组做差分，能得到差分数组。展开写一下：

a[1] = d[1] a[2] = d[1] + d[2] a[3] = d[1] + d[2] + d[3]

发现规律了吗？原数组的第 k 项，等于差分数组前 k 项之和。这就是为什么最后“恢复”原数组只需要对差分数组做一次前缀和。

我备考的时候画过一张对比图：一列数从上到下排开，旁边一列是相邻差，旁边一列是累加和。看多了之后你会有一种感觉：前缀和是“汇总”，差分是“分解”。任何关于前缀和的题，都有可能在差分方向上有对应版本。

1.3 为什么区间修改只需动两个点

这是差分的精髓，值得认真推导一遍。

假设我们对原数组 a 执行了一次区间加操作：把 [l, r] 的每个元素都加上 x。现在看差分数组 d 的变化。

对于任意位置 i（1 ≤ i ≤ n），d[i] = a[i] - a[i-1]。区间加操作只影响了 a[l] 到 a[r] 这个范围内的值，所以：

• 在 i = l 处，a[l] 增加了 x，而 a[l-1] 没变，所以 d[l] 增加了 x。
• 在 l+1 到 r 这段内部，a[i] 和 a[i-1] 同时增加了 x，差值不变，所以 d[i] 不变。
• 在 i = r+1 处，a[r] 增加了 x，而 a[r+1] 没变，所以 d[r+1] 减少了 x。
• 其他位置一律不受影响。

结论是：一次区间加操作，只需要修改 d[l] += x 和 d[r+1] -= x 这两个位置。这就是差分数组能高效解决问题的数学基础。

很多初学者会在这里卡住，原因是没有抓住“内部差值不变”这个关键点。只要是整段同时加同一个值，段内相邻两个数的大小关系完全不变，那么变化就只会发生在段的“入口”和“出口”两个边界上。

2. 一维差分：从理解到写代码

2.1 从原数组构造差分数组

最简单的方式，就是直接按照定义来：遍历原数组，d[i] = a[i] - a[i-1]。

更实用的一种方式是利用一次“区间加”的等价操作。我们已知初始数组 a 全是 0，而 a[i] 的最终值也可以看成是从 0 开始、在区间 [i, i] 上加 a[i] 得到的结果。所以对于每个位置 i，我们可以调用 add(i, i, a[i]) 来完成整个差分数组的构造。

这个思路初看有点绕，但理解之后非常方便：你不需要单独记住“差分构造”和“区间加”两套逻辑，它们本质上是同一件事。我在实际写题时，习惯了把差分数组初始化为全 0，然后统一通过 add 函数来建立数组，这样就不容易漏改边界。

2.2 区间修改的两步操作

一段代码就能说明白：

void add(int l, int r, long long v) { d[l] += v; d[r + 1] -= v; }

注意第二个修改点是 r+1，而不是 r。这个错误我在初学时犯过不下三次，每一次都是样例能过、提交超时或者结果错乱。原因是：如果只改 d[l] 而不在 r+1 处减回去，那前缀和恢复时增量会一直往后蔓延到数组末尾，区间 [l, r] 之外的区域也会被错误修改。

这里有一个边界问题：如果 r == n，那么 d[n+1] 已经超出了字符串范围。所以差分数组 d 的大小至少要开成 n+2，并且对 d[n+1] 的修改可以写，但恢复原数组时不要访问它。这也是为什么很多人把数组下标从 1 开始用，而不是从 0 开始。

2.3 还原原数组：一步前缀和

所有区间加操作都记录到差分数组之后，最后一步是把差分数组“恢复”成原数组。

for (int i = 1; i <= n; ++i) { ans[i] = ans[i - 1] + d[i]; }

ans[i] 就是最终数组中第 i 个位置的值。注意 ans[i] 依赖的是 ans[i-1]，所以必须按顺序从左到右遍历。

很多新手刚接触时会把 ans[i] 直接写成 d[i]，然后发现结果完全对不上。原因是 d[i] 存的是“当前位置相对于前一个位置的变化量”，它不是位置的值。只有把前面所有变化量累积起来，才是真实值。

2.4 一维差分的经典模板代码

下面是我习惯用的一个完整模板，可以直接抄走。这个模板用 1-index，数组多开两个位置，避免访问越界。

#include <bits/stdc++.h> using namespace std; int main() { int n, m; cin >> n >> m; vector<long long> d(n + 2, 0); auto add = [&](int l, int r, long long v) { d[l] += v; d[r + 1] -= v; }; while (m--) { int l, r; long long v; cin >> l >> r >> v; add(l, r, v); } vector<long long> ans(n + 1, 0); for (int i = 1; i <= n; ++i) { ans[i] = ans[i - 1] + d[i]; cout << ans[i] << (i == n ? '\n' : ' '); } return 0; }

模板虽然简单，但有三个细节建议养成本能：d 开 n+2 而不是 n；add 函数第二个修改点写 r+1 而不是 r；ans 恢复时用 long long，防止累加溢出。

3. 二维差分：从线到面的思维跃迁

3.1 先复习二维前缀和的容斥公式

二维差分不像一维差分那样直观，需要对二维前缀和先有感觉。

二维前缀和 s[i][j] 表示从 (1,1) 到 (i,j) 这个矩形区域内所有元素的和。递推公式是：

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

中间减去 s[i-1][j-1] 是因为左上角那一块被加了两次，需要去重。这种“加两块、减一块”的容斥思想，在二维差分里会再次出现。

3.2 四个角操作背后的容斥逻辑

现在的问题变成：给你一个全 0 的 n 行 m 列矩阵，有 q 次操作，每次把左上角 (x1, y1) 到右下角 (x2, y2) 这个矩形区域内的所有元素都加上 v。要求最后输出整个矩阵。

如果用一维差分的思路类推：一维区间是两个端点，二维矩形自然就想到四个角。具体操作是：

void addRect(int x1, int y1, int x2, int y2, long long v) { d[x1][y1] += v; d[x2 + 1][y1] -= v; d[x1][y2 + 1] -= v; d[x2 + 1][y2 + 1] += v; }

为什么右下角是加 v 而不是减 v？我用一个小例子来说清楚。

假设有一个 4×4 的矩阵，给区域 (2,2) 到 (3,3) 加上 v。经过上面四个操作后再做二维前缀和，你会发现：

• 只有 (2,2) 到 (3,3) 区域内的元素最终多了 v；
• 从 (2,4) 往右的部分，因为右上角有一个 -v，增量被抵消；
• 从 (4,2) 往下的部分，因为左下角有一个 -v，增量被抵消；
• 从 (4,4) 到矩阵末尾这个右下角区域，会被右上和左下的两个 -v 连续作用，减了两次，所以必须在右下角放一个 +v 补回来。

这和二维前缀和容斥公式里的“减一次重复区域”是同一个道理。如果只加三个角，右下角的区域会多减一个 v，结果完全错误。

理解不了的时候怎么办？我建议你拿一张方格纸，在 4×4 的小矩阵上把 d 数组的四个角标记出来，然后手动做二维前缀和，把每个格子的累计值写出来。你会直观看到 v 的影响范围正好是一个矩形。

3.3 二维差分的完整模板

#include <bits/stdc++.h> using namespace std; int main() { int n, m, q; cin >> n >> m >> q; vector<vector<long long>> d(n + 2, vector<long long>(m + 2, 0)); auto addRect = [&](int x1, int y1, int x2, int y2, long long v) { d[x1][y1] += v; d[x2 + 1][y1] -= v; d[x1][y2 + 1] -= v; d[x2 + 1][y2 + 1] += v; }; while (q--) { int x1, y1, x2, y2; long long v; cin >> x1 >> y1 >> x2 >> y2 >> v; addRect(x1, y1, x2, y2, v); } vector<vector<long long>> ans(n + 1, vector<long long>(m + 1, 0)); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { ans[i][j] = ans[i - 1][j] + ans[i][j - 1] - ans[i - 1][j - 1] + d[i][j]; } } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { cout << ans[i][j] << " \n"[j == m]; } } return 0; }

这里有一个我自己的小技巧：如果你对二维容斥很不放心，可以先把每一行当成一维差分来做，也就是按行做 add 操作，然后单独对每行做前缀和。这样做虽然没有直接使用二维前缀和那么快，但调试起来非常直观。当你通过这种方式把思路验证清楚之后，再切换到标准的四角操作，就不容易出错了。

4. 四种基础题型：刷题时怎么想到差分

4.1 区间加后还原数组

这是最基础也是最直接的差分应用。题目一般这样说：原数组初始为 0，给你 m 次区间加操作，最后输出每个位置的值。

解题思路非常固定：读取操作的同时调用 add(l, r, v)，所有操作完成后做一次前缀和，然后输出。

这类题的变形是：给你一个最终数组，问是否能通过若干次“区间加 1”操作得到。解法是把原数组做差分，看差分数组中正数之和和负数绝对值之和是否相等。因为一次区间加 1 的等价差分操作是 d[l]++ 和 d[r+1]--，最终所有 d[i] 应该能通过正负配对归零。这个配对思想在很多思维题里都会用到。

4.2 覆盖次数统计类问题

有 n 个区间 [l_i, r_i]，问每个点被多少个区间覆盖。

通常数值范围很大，n 和坐标范围都是 10^5 级别。暴力做法是遍历每个区间再遍历区间内每个点，复杂度 O(n×len)，完全不可行。差分解法是：初始化差分数组全 0，对每个区间执行 add(l, r, 1)，最后统一做前缀和。ans[i] 就是点 i 被覆盖的次数。总复杂度 O(n + maxCoordinate)。

这个思想还可以扩展到带权覆盖、区间重叠最大次数、时间线上同时进行的事件数量统计等场景。只要看到“给很多区间，询问每个点被覆盖的次数”，第一反应就应该是差分。

4.3 把差分作为贪心工具

有一类非典型的差分题，题目里完全没有提到“区间修改”，但你要把问题转化成差分来处理。

典型题：给你一个数组 a，每次操作可以选择一个连续区间，把区间内所有数都减 1。问最少操作多少次能把整个数组变成全 0。

直接贪心很难下手，但用差分视角看会非常清晰。令 d[i] = a[i] - a[i-1]。一次把区间 [l, r] 减 1 的操作，等价于 d[l] 减 1、d[r+1] 加 1。要让 a 变成全 0，等价于让所有差分值归零。每次操作会把一个正的差分值和一个负的差分值同时向 0 靠近，因此最少操作次数就是差分数组中正数之和（也等于负数绝对值之和）。把题目建模成差分之后，原来无从下手的贪心题变成了非常简单的一行代码计算。

这类题是“题目不会告诉你用差分，但最优解法就是差分”的典型代表。我在竞赛里见过很多次，建议把它当作思维拓展题反复练习。

4.4 “端点标记”类问题

有一类问题的共性是：给出一系列在某一维度上连续延伸的事件，要求统计某种累积效果。比如若干个时间段，每个时间段内有一个恒定速率的变化量，问某个时间点的总变化值。

这种问题非常适合差分。对每个时间段，在起点处打一个 +v 的标记，在终点后一个位置打一个 -v 的标记，然后做一次时间维度的前缀和，每个时间点的累积值就出来了。

这类题目把“区间”抽象成了“事件区间”，但本质和普通的 4.1 完全一样。识别特征是：连续区间、批量累加、区间互相重叠。看到这三个特征，就可以往差分上靠。

5. 常见问题与排查实录

5.1 边界写错导致区间失效

症状：样例能过，但提交后答案错得离谱，而且往往是后面位置的值多或者少一个固定值。

原因大多是 add 的第二个修改点写错。我见过有人写成 d[r] -= v，然后整个区间加的范围变成 [l, r-1]。也有人忘记判断 r == n 的情况，导致 d[n+1] 越界后数据被破坏。

建议：不管数据范围多小，差分数组一律开 n+2；add 函数里直接写 d[r+1] -= v，不要先判断再写。恢复原数组时只需要遍历 1 到 n，d[n+1] 被忽略即可。这样逻辑最干净。

5.2 恢复差分时没做前缀和

症状：输出结果看起来“有点规律但每个数都不对”，比如第一个位置正确、第二个位置是第一个加上某个数、但始终不等于真实值。

原因我前面已经强调过：d[i] 是变化量不是值，必须做前缀和累加。这个问题在考试中非常常见，因为大家很容易把“差分数组”和“原数组”的概念混在一起。

调试技巧：遇到输出不对时，把差分数组 d 和原数组 a 并排打印出来，逐项检查 d[i] 是否等于 a[i] - a[i-1]。如果确认 d 对而 a 错，就是恢复过程的问题。

5.3 二维差分容斥符号记混

症状：二维矩阵中，修改结果出现在矩形右上角或右下角，或者矩形内部多了一部分、少了一部分。

区分方法：把四个角按逆时针顺序背下来。每次操作写完之后，用一个 2×2 的矩形代入验证一遍。比如给 (1,1) 到 (1,1) 加 1，四个操作应为：d[1][1]+1、d[2][1]-1、d[1][2]-1、d[2][2]+1。手动算一下这个小例子，10秒钟就能确认自己有没有写反。

5.4 下标从 0 开始引发的连锁错误

很多语言里数组天然从 0 开始。如果你把差分数组下标也设计成 0 开始，那么区间 [l, r] 的 add 操作要写成：d[l] += v，d[r+1] -= v。注意 r+1 可能等于 n，所以数组长度至少是 n+1。

我个人的建议是：在写算法题时主动使用 1-index，把 a[0] 空出来不用。这样差分边界逻辑永远是 d[l] 和 d[r+1]，不用去想“要不要加一避开头尾”，能少掉很多小 bug。

5.5 数据范围与整数溢出

差分数组里的值是可能很大的。假如 n 是 10^5，m 是 10^5，每次加的 v 是 10^9，那么最终 ans 里的最大值能达到 10^14。int 的最大值约 2.1×10^9，直接爆掉。

建议所有差分数组、前缀和数组、最终答案数组全部使用 long long。即使题面给定的输入看起来在 int 范围内，区间累加之后就可能翻很多倍。这是我吃过亏之后养成的习惯，现在只要碰到差分和前缀和，无脑用 long long 就对了。

下面的表格是一些典型问题的速查思路，我经常在复习时翻看：

6. 个人实操体会与练习建议

说一点我自己的学习经历。我刚开始学差分时，一直在背 add 函数的写法，结果换了个题目语境就蒙了。后来我发现一个更稳妥的学习路径：先拿一维差分的模板，把“区间加后输出数组”这道题用纸笔演算一遍，从定义 d[i] = a[i] - a[i-1] 一步步推导为什么是修改两个端点。这个过程虽然慢，但比刷十道模板题更能建立长期记忆。

二维差分刚接触时非常容易翻车，我的建议是先不要碰代码，找一个 4×4 的矩阵，手动执行一次 addRect，再用二维前缀和做一遍展开，亲眼看看每个格子的值是怎么变化的。当你能在纸上把四个角的变化过程讲清楚，二维差分就再也不是难点。

练习顺序上，我建议按照一维区间加模板题、覆盖次数统计、一维最小操作贪心、二维矩形加模板题的顺序推进。基本覆盖了从模板到思维的全部阶段。等这些题都能稳定 AC 之后，可以尝试把差分和扫描线、树上差分这些进阶内容结合起来看，会发现前面打下的基础非常有用。

最后分享一个实操中的小技巧：如果某道题你判断出要使用差分，但又担心边界条件写错，可以在所有操作完成之后，用一个自己写的小 case 检查：比如 n=5，处理 [2,4] 加 3，然后打印 ans 数组。如果中间三个数都变成了 3，端点没有误改，说明基本逻辑没问题。这个小习惯帮我避免了很多低级错误，你也可以试试。