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

先聊一个老生常谈的话题很多人刷题刷到“差分”这个知识点时第一反应是“又是一个看起来很数学的东西”然后容易被名字劝退。但实际接触下来你会发现差分的核心思想只用一个生活场景就能讲清楚——记录相邻两天的体重变化量一天天累加回去就能知道每一天的体重。就这么简单。在算法竞赛里差分一般指差分数组它是前缀和的逆运算专门用来高效处理“区间批量修改”这一类问题。比如说有一个长度为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 处打开水龙头在 r1 处放一个停水挡板。最后把水流从头到尾累积一遍每个水槽里接到的水量就是最终值。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 的变化。对于任意位置 i1 ≤ i ≤ nd[i] a[i] - a[i-1]。区间加操作只影响了 a[l] 到 a[r] 这个范围内的值所以在 i l 处a[l] 增加了 x而 a[l-1] 没变所以 d[l] 增加了 x。在 l1 到 r 这段内部a[i] 和 a[i-1] 同时增加了 x差值不变所以 d[i] 不变。在 i r1 处a[r] 增加了 x而 a[r1] 没变所以 d[r1] 减少了 x。其他位置一律不受影响。结论是一次区间加操作只需要修改 d[l] x 和 d[r1] - 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; }注意第二个修改点是 r1而不是 r。这个错误我在初学时犯过不下三次每一次都是样例能过、提交超时或者结果错乱。原因是如果只改 d[l] 而不在 r1 处减回去那前缀和恢复时增量会一直往后蔓延到数组末尾区间 [l, r] 之外的区域也会被错误修改。这里有一个边界问题如果 r n那么 d[n1] 已经超出了字符串范围。所以差分数组 d 的大小至少要开成 n2并且对 d[n1] 的修改可以写但恢复原数组时不要访问它。这也是为什么很多人把数组下标从 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; vectorlong 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); } vectorlong 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 开 n2 而不是 nadd 函数第二个修改点写 r1 而不是 rans 恢复时用 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; vectorvectorlong long d(n 2, vectorlong 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); } vectorvectorlong long ans(n 1, vectorlong 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[r1]--最终所有 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[r1] 加 1。要让 a 变成全 0等价于让所有差分值归零。每次操作会把一个正的差分值和一个负的差分值同时向 0 靠近因此最少操作次数就是差分数组中正数之和也等于负数绝对值之和。把题目建模成差分之后原来无从下手的贪心题变成了非常简单的一行代码计算。这类题是“题目不会告诉你用差分但最优解法就是差分”的典型代表。我在竞赛里见过很多次建议把它当作思维拓展题反复练习。4.4 “端点标记”类问题有一类问题的共性是给出一系列在某一维度上连续延伸的事件要求统计某种累积效果。比如若干个时间段每个时间段内有一个恒定速率的变化量问某个时间点的总变化值。这种问题非常适合差分。对每个时间段在起点处打一个 v 的标记在终点后一个位置打一个 -v 的标记然后做一次时间维度的前缀和每个时间点的累积值就出来了。这类题目把“区间”抽象成了“事件区间”但本质和普通的 4.1 完全一样。识别特征是连续区间、批量累加、区间互相重叠。看到这三个特征就可以往差分上靠。5. 常见问题与排查实录5.1 边界写错导致区间失效症状样例能过但提交后答案错得离谱而且往往是后面位置的值多或者少一个固定值。原因大多是 add 的第二个修改点写错。我见过有人写成 d[r] - v然后整个区间加的范围变成 [l, r-1]。也有人忘记判断 r n 的情况导致 d[n1] 越界后数据被破坏。建议不管数据范围多小差分数组一律开 n2add 函数里直接写 d[r1] - v不要先判断再写。恢复原数组时只需要遍历 1 到 nd[n1] 被忽略即可。这样逻辑最干净。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] vd[r1] - v。注意 r1 可能等于 n所以数组长度至少是 n1。我个人的建议是在写算法题时主动使用 1-index把 a[0] 空出来不用。这样差分边界逻辑永远是 d[l] 和 d[r1]不用去想“要不要加一避开头尾”能少掉很多小 bug。5.5 数据范围与整数溢出差分数组里的值是可能很大的。假如 n 是 10^5m 是 10^5每次加的 v 是 10^9那么最终 ans 里的最大值能达到 10^14。int 的最大值约 2.1×10^9直接爆掉。建议所有差分数组、前缀和数组、最终答案数组全部使用 long long。即使题面给定的输入看起来在 int 范围内区间累加之后就可能翻很多倍。这是我吃过亏之后养成的习惯现在只要碰到差分和前缀和无脑用 long long 就对了。下面的表格是一些典型问题的速查思路我经常在复习时翻看题目特征推荐思考方向关键点区间加后输出最终数组一维差分 前缀和恢复add(l, r, v)区间覆盖次数统计差分 前缀和每个区间 add(l, r, 1)最少区间减操作归零差分转化为正负配对正数总和 负数绝对值总和二维矩形加后输出矩阵二维差分 二维前缀和四角容斥操作时间段累积效果时间轴差分起点 v、终点后 -v6. 个人实操体会与练习建议说一点我自己的学习经历。我刚开始学差分时一直在背 add 函数的写法结果换了个题目语境就蒙了。后来我发现一个更稳妥的学习路径先拿一维差分的模板把“区间加后输出数组”这道题用纸笔演算一遍从定义 d[i] a[i] - a[i-1] 一步步推导为什么是修改两个端点。这个过程虽然慢但比刷十道模板题更能建立长期记忆。二维差分刚接触时非常容易翻车我的建议是先不要碰代码找一个 4×4 的矩阵手动执行一次 addRect再用二维前缀和做一遍展开亲眼看看每个格子的值是怎么变化的。当你能在纸上把四个角的变化过程讲清楚二维差分就再也不是难点。练习顺序上我建议按照一维区间加模板题、覆盖次数统计、一维最小操作贪心、二维矩形加模板题的顺序推进。基本覆盖了从模板到思维的全部阶段。等这些题都能稳定 AC 之后可以尝试把差分和扫描线、树上差分这些进阶内容结合起来看会发现前面打下的基础非常有用。最后分享一个实操中的小技巧如果某道题你判断出要使用差分但又担心边界条件写错可以在所有操作完成之后用一个自己写的小 case 检查比如 n5处理 [2,4] 加 3然后打印 ans 数组。如果中间三个数都变成了 3端点没有误改说明基本逻辑没问题。这个小习惯帮我避免了很多低级错误你也可以试试。