1. 从一道卡的题目说起：区间操作的暴力困境

先讲个真实场景。前段时间某交流群里有人贴了一道题，大意是：有一个长度为 n 的数组，初始全是 0，现在有 m 次操作，每次把区间 [l, r] 内的所有数统一加上一个值 c，问所有操作结束后数组变成什么样。n 和 m 的规模都在十万级别。

底下评论区清一色的回答是"差分"。提问的人一脸懵：差分是什么？为什么我看到这种题就只知道两重循环？

其实这种反应太正常了。遇到"区间加"这种描述，第一反应是写循环去遍历区间里每个位置，这是人脑最自然的想法。但你想过没有，如果每次操作都遍历 [l, r]，极端情况下每次都是全区间 [1, n]，m 次操作就是 m × n 次赋值，十万乘十万是 100 亿次运算，在绝大多数评测环境里直接给你跑出五分钟都跑不完的体验。

那有没有办法让"区间加"这个动作本身变快？差分就是干这个的。

在我拆开讲之前，你先记住一句话：差分解决的核心问题，是把"对一整段区间做修改"压缩成"只修改区间的两个端点"。至于为什么能这样压缩，后面我会用买菜找零钱的例子给你讲透。

这篇文章我不会堆术语，而是从本质逻辑出发，把差分的原理、数组构建、题型识别、易错边界全部过一遍。不管你是刚接触算法的新手，还是刷题刷到怀疑人生的老手，看完都应该能对差分形成一套自己的判断框架。

2. 差分的本质：区间修改如何变成端点修改

2.1 从找零钱理解"增量"思想

你去买 8 块钱的东西，给了老板 100 块，老板要找 92 块。老板有两种做法：一种是真一张张数 92 块钱给你，另一种是先在账本上记一笔"找零 92"，等结账的时候再统一轧账。

第一种适合单次交易，第二种适合一天有几百笔交易的情况——如果每笔都当场清点，收银台得排队到天荒地老；但如果只记账、最后统一结算，每笔交易只需记一个数字，结算时把账本加起来就行。

差分的思路就是第二种。它不追求"每次操作后立刻更新数组"，而是把每个区间操作转换成一种"记账"——只在区间端点记下变化量，最后统一做一次处理，把账轧平。

这里的"轧平"在代码里叫"求前缀和"。

2.2 差分数组的定义与构造

给定原数组 a，下标从 1 开始：

a = [0, a1, a2, a3, ..., an]

构造差分数组 d，规定：

• d[1] = a[1]
• d[i] = a[i] - a[i-1]，对 i 从 2 到 n

也就是说，d 里存的是原数组相邻两项之间的差值。你可能觉得这有啥用？一堆正负号能干嘛？

关键在这里：已知 d 求 a 的过程，就是前缀和。你看：

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

所以，差分就是前缀和的逆运算：前缀和把数组压缩成累积值，差分把数组拆成变化量。

现在问题来了：如果我给 a 的区间 [l, r] 统一加 c，反映到 d 上会怎样？

2.3 区间修改的差分表现

假设原始数组 a，差分数组 d。现在执行操作：a[l] 到 a[r] 每个元素都加 c。

我们只观察差分数组里哪些位置会发生变化：

• 在位置 l，a[l] 变大 c，a[l-1] 没变，所以 d[l] = a[l] - a[l-1] 会变大 c →d[l] += c
• 在位置 r+1，a[r+1] 没变（如果 r+1 <= n），a[r] 变大 c，所以 d[r+1] = a[r+1] - a[r] 会变小 c →d[r+1] -= c
• 中间位置 l < i <= r，a[i] 和 a[i-1] 都变大 c，差值不变 → d[i] 不变

你看，一个长达一整个区间的操作，在差分数组里就变成了两个点的修改。无论区间多长，都只改两个数。这就是"区间修改转端点修改"的全部秘密。

等所有操作都记录完了，只需要对 d 做一次前缀和，就能还原出最终的 a。复杂度从 O(m×n) 降到 O(m + n)。

2.4 一个反面理解：为什么不能用"每次暴力更新差分再还原"？

很多人学差分会走进一个误区：以为差分数组也要跟着原数组实时更新。如果每操作一次就做一次前缀和还原，那复杂度还是 O(m×n)，一点没省。

差分的精髓在于延迟结算：先攒着所有增量信息，最后一次性还原。这和我们记账先不付钱、月底统一结清是一个道理。如果你每笔都当场结清，那记账的意义就没了。

所以请反复提醒自己：差分数组的构建可以一次性做完，区间修改只碰端点，最后统一求一次前缀和。不要中途反复还原。

3. 一维差分的基础题型与代码范式

3.1 题型一：多次区间加后，求最终数组

这是最经典、也是所有差分题的基础。给定长度为 n 的初始数组（可能全零，也可能有初值），m 次操作，每次把 [l, r] 加上 c，最后输出完整数组。

处理手法分三步。第一步，根据初始数组构建差分数组。第二步，对每次操作执行 d[l] += c、d[r+1] -= c。第三步，对差分数组做前缀和，得到操作后的原数组。

如果初始数组不为零，构建差分时直接用原数组相邻差即可，不需要额外初始化成全零再逐个加一遍。这段逻辑写成代码：

#include <bits/stdc++.h> using namespace std; const int N = 100005; long long a[N], d[N]; int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i]; d[i] = a[i] - a[i-1]; // 构建差分 } while (m--) { int l, r; long long c; cin >> l >> r >> c; d[l] += c; d[r+1] -= c; // 注意 r+1 可能等于 n+1，数组要开够 } for (int i = 1; i <= n; i++) { a[i] = a[i-1] + d[i]; // 前缀和还原 cout << a[i] << " \n"[i == n]; } return 0; }

代码短，就三行核心逻辑，但每次写完我都建议你手动跑一遍样例确认边界。比如 l = 1 时，d[1] 会被加上 c，这表示区间从第一个元素就开始变化，合理。r = n 时，d[n+1] 会减去 c，此时数组要开到 n+2 才行，不然写 d[n+1] 直接越界。

3.2 题型二：区间加多次后，多次区间求和

如果题目从"输出最终数组"升级成"操作几次后问一次区间和"，或者"先做一堆区间加，再来一堆区间查询"，只靠差分就不够了。

思路是把差分和前缀和叠加使用。先对所有区间加操作打上差分标记，一次性还原出最终的 a 数组；然后对最终的 a 再做一次前缀和，得到前缀和数组 s；查询区间 [l, r] 的和就用 s[r] - s[l-1] 回答，O(1)。

这个套路我管它叫"差分负责修改，前缀和负责查询"。两者是天生一对，很多人只学了前缀和、又单独学了差分，却没意识到它们组合起来的威力。

这里有个容易踩的坑：如果你先对差分数组做前缀和还原出 a，然后又对 a 做前缀和，这两步不能合并成"对 d 做两次前缀和"吗？

我建议你推导一下。第一次前缀和：a[i] = a[i-1] + d[i]。第二次前缀和：s[i] = s[i-1] + a[i]。如果你用 d 直接做两次累加，等于在算带权重的累加，得到的并不是想要的区间和的工具数组。所以老老实实分两步，不要偷懒。

3.3 题型三：区间加上等差序列，引入二阶差分

这是基础题里比较隐蔽的一种变式。操作不再是"区间统一加 c"，而是"区间 [l, r] 内第 k 个元素加 k × step"或类似等差递增的增量。

此时一看题型二里的一阶差分就不够用了——因为一阶差分只能处理"所有元素加同一个常数"的情况。等差序列的特点是相邻两个位置的增量差恒定为 step，这个"增量的增量"是常数，正好落在二阶差分管辖的范围内。

具体做法不展开写，只指个方向：对原数组做两次差分得到二阶差分数组 d2，区间等差加会对应到 d2 上最多四个点的修改。当你遇到"加的值不是常数、而是随位置线性变化"的题目，先想二阶差分。

不过我要提醒一句，这类题在大厂笔试里的出现频率其实不高，很多刷题者在这上面花大量时间，结果考试反而不考。我的建议是：把一维差分、二维差分吃透，二阶差分知道原理即可，不必死磕偏题。

3.4 差分数组在初始化时的一个理解误区

我看到过不少讲解将初始化写成"原数组 all zeros 的前提下，每次区间加 c，等效于 d[l] += c、d[r+1] -= c"，然后让读者自己推到原数组有初值的情况。很多人推到一半就卡住，以为初始值还要额外处理。

实际上原数组有初值时，差分数组的构建就是 d[i] = a[i] - a[i-1]，区间修改的操作完全相同，不需要把初值当作特殊操作分批次加入。因为差分数组本身就完整描述了原数组的所有信息，后续区间加只修改端点位置的变化量，最后前缀和还原时，初值自然就包括在内了。

初值、区间加互不干扰，这是我当年学了半天才想明白的点，写在这里帮你看少走弯路。

4. 二维差分：矩阵区域修改的容斥写法

4.1 为什么二维不能直接照搬一维

如果问题升级成"给出一个 n×m 的矩阵，每次把一个子矩阵所有元素加 c，最后输出整个矩阵"，一维差分是不是直接扩展成二维就完了？

逻辑方向是对的，但实现细节稍有不同。一维区间只有左右两个端点，二维子矩阵有四个角。按照一维差分"只改端点"的思路，二维差分应该只在这四个角上做标记。

那四个角怎么标记？直接填 c 吗？不对。你不能简单地四个角都加 c，那样搞混了区域归属。正确的做法是参考二维前缀和的容斥原理。

4.2 二维差分的四角标记与容斥

假设子矩阵左上角是 (x1, y1)，右下角是 (x2, y2)，差分数组叫 diff。

正确的操作是：

• diff[x1][y1] += c
• diff[x2+1][y1] -= c
• diff[x1][y2+1] -= c
• diff[x2+1][y2+1] += c

为什么有加有减？你可以把它理解为：在 (x1, y1) 这个点开始，向右向下同时播撒增量 c，这个"播撒"的效果会覆盖整个从 (x1, y1) 到矩阵无穷远处的区域。但题目要求的只到 (x2, y2)，所以要在右侧和下方"截断"。截断时，多减出去的区域又被减了两次，需要加回来一次——这就是容斥。

等我用简单的图式解释一下。想象 diff 做二维前缀和后，每个位置的值等于"左上角区域所有标记的和"。你在 (x1, y1) 加 c，那么从 (x1, y1) 向右下方向的整个区域都会因前缀和传播而获得 c。为了只保留到 (x2, y2)，在 (x2+1, y1) 减 c，切断竖直方向的传播；在 (x1, y2+1) 减 c，切断水平方向的传播。但右下角 (x2+1, y2+1) 那块区域被两个方向的减法都影响到，相当于被减了两次 c，所以最后要再加回 c。

4.3 二维差分的构建与还原代码

和一维一样，如果原矩阵有初值，可以先按行构建差分，也可以直接用"原矩阵相邻差"的方式手动构造。但更省事的办法是：把"赋予初值"这件事也当成一次子矩阵加 c 的操作来执行——每个点 (i, j) 的初值 a[i][j] 等价于对子矩阵 (i, j) 到 (i, j) 加 a[i][j]。

这样做的好处是，你只需要实现一个 add 函数，初始化、操作、还原都用同一套代码，不容易写错。代码模板：

const int MAXN = 1005; long long diff[MAXN][MAXN]; void add(int x1, int y1, int x2, int y2, long long c) { diff[x1][y1] += c; diff[x2+1][y1] -= c; diff[x1][y2+1] -= c; diff[x2+1][y2+1] += c; } int main() { int n, m, q; cin >> n >> m >> q; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { long long val; cin >> val; add(i, j, i, j, val); // 初值当单点加 } } while (q--) { int x1, y1, x2, y2; long long c; cin >> x1 >> y1 >> x2 >> y2 >> c; add(x1, y1, x2, y2, c); } // 二维差分还原：先对每行做前缀和，再对每列做前缀和 for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1]; // 此时 diff 数组就是最终矩阵 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) cout << diff[i][j] << " \n"[j == m]; } return 0; }

这里还原用到的式子 diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1] 实际上就是二维前缀和公式，只是就地覆盖、省一个数组而已。如果你忘了这个公式，可以回忆一个事实：当前点的值 = 上方累积值 + 左方累积值 - 左上角重复计算值 + 自身标记。

4.4 二维差分在实际题中的变体

二维差分不仅仅出现在算法竞赛里。比如图像处理中的"区域亮度调整"、电子表格批量区域填充、游戏地图里某个矩形区域刷怪，底层逻辑都是同一套：矩形区域批量修改，最后统一读取。

有些题不是直接给你子矩阵坐标，而是给"中心点 (cx, cy) 为中心、边长为 k 的矩形"，需要你先把坐标算成 x1 = cx - k/2 等，再调用 add。记得先做边界裁剪，把超出矩阵范围的部分 clip 掉，否则数组越界或者容斥坐标乱掉。

我实际写题时发现，二维差分最容易出错的地方不是公式本身，而是坐标计算：x2+1、y2+1 在矩阵边缘会到 n+1、m+1，所以 diff 数组至少要开 (n+2)×(m+2)。很多新手开成 n×m，一跑就崩，还以为是公式错了。

5. 差分最容易翻车的五个边界问题

5.1 问题一：r+1 越界

一维差分里 d[r+1] -= c，如果 r = n，就写到 d[n+1]。很多人的数组刚好开成 n 大小，运行时报错或者内存越界。我的习惯是数组一律多开两个单位：差分大小开 n+2，二维开 (n+2)×(m+2)。多几个 int 的空间成本几乎为零，但能省掉大量排查越界的痛苦。

5.2 问题二：下标从 0 还是从 1 开始

C++ 选手通常习惯从 1 开始读入，这样 d[l] += c、d[r+1] -= c 的语义最直观。但很多内置数组、Python list 默认从 0 开始，此时区间 [l, r] 加 c 应该写 d[l] += c、d[r+1] -= c，r+1 越界到 n 时不需要（也不能）写，因为最后前缀和只遍历到 n-1。

我见过不少人从 0 开始的题硬套从 1 开始的模板，结果所有位置的标记全部错位一位。建议你在代码开头就定死一种习惯，别混着用。

5.3 问题三：把"端点修改"误写成"区间内每个位置都修改"

这是个很诡异但真实存在的错误。有人理解了差分的大方向，但代码里写的是 for (int i = l; i <= r; i++) d[i] += c，理由是"反正最后要求前缀和"。这一写，复杂度又回去了，而且因为差分标记被重复叠加，结果还不对。

差分的高效完全建立在"只改两个端点"上。如果你发现自己写成了循环，立刻停下来检查思路。

5.4 问题四：数据类型溢出

差分数组里累计的 c 可能很大，前缀和还原后可能超过 int 范围。尤其是多次区间加的 c 累加到同一位置，极端情况下 m 次操作叠加，值域可能到几亿甚至几十亿。我用 long long 已经是肌肉记忆，但偶尔会见别人用 int 然后 WA 在最后一个数据点。排查"明明逻辑对但 WA"的时候，先看数据类型。

5.5 问题五：离散化场景下不能直接开数组

如果区间的 l、r 范围极大（比如 1 到 10^9），开数组显然不现实。这时候可以把所有操作涉及到的端点收集起来，排序去重，映射到连续的紧凑坐标上，再做差分。注意此时区间加 c，需要用"离散化后的坐标"操作，并且在最后还原时，每段的实际长度不一定是 1，需要乘上该段的长度。

这类题已经算差分的进阶用法，但你在基础阶段至少要知道有这回事。真正到笔试面试时，数据范围往往没那么夸张，别被吓到。

6. 差分题目如何识别以及后续可以扩展的方向

6.1 一道题什么时候该想到差分

我的判断标准就三条，几乎不会漏判：

• 题目描述里有"区间"或"子矩阵"
• 操作是"所有元素统一加一个值"或"统一减一个值"
• 操作次数多、目标区间范围大，暴力复杂度明显不可接受

三条同时满足时，直接往差分上想。如果还牵扯到多次操作后查询某个前缀信息，那基本就是"差分 + 前缀和"的组合套餐。

反过来，如果操作不是统一加一个值，而是"乘一个值""每个位置加不同的函数值"，差分就不太合适了。那种情况一般交给线段树、分块这类更通用的数据结构，当然复杂度也高不少。差分能做的就是这种"均匀批量修改"的场景，理解这个边界，你就不容易把差分用错地方。

6.2 前缀和、差分、线段树的配合关系

拿区间问题做个简单比较：

差分强在"大量修改、最终一次性查询"的批量场景。如果修改中间穿插着查询，差分就施展不开了，那得上树状数组或线段树。你把这个关系理清后，做题就不会再"看见区间就想套线段树"了——很多题用数据结构能做，但差分更简单更快。

6.3 树上差分：差分思想的高级延伸

如果你已经吃透了一维、二维差分，我建议你可以扫一眼树上差分。它的核心思维是一脉相承的：树上的路径修改也可以拆成端点操作，比如对从 u 到 v 的路径上所有点加 c，可以转化为对 u 加 c、v 加 c、LCA 减 c、LCA 的父节点再减 c，最终做一次 DFS 汇总。

我第一次看到这个转化时挺震撼的——路径这种"曲线"信息居然也能被压缩成四个点的标记。虽然基础题型总结到二维差分就够应付大部分入门题了，但了解树上差分能帮你看清差分思想的生命力：凡是"批量修改、最后汇总"的问题，都有差分的影子。

6.4 刷题顺序与心态建议

最后说说我个人在带新人（包括我自己以前学的时候）时验证过的刷题顺序：先做三分之一维差分的裸题，确保闭着眼睛能写出 d[l] += c、d[r+1] -= c 然后前缀和还原；再做原数组带初值、多次区间加后求最终数组；接着做区间修改 + 区间查询的复合题；最后挑战二维差分的模板题。顺序千万别反过来——有些人一上来就做二维，被容斥绕晕后连一维都开始怀疑。

差分入门不难，难的是把它融入你的条件反射里。我在自己刷题时有个习惯：每道题交之前，都手动构造一个 n=5 的小样例把过程走一遍，确认端点标记得对、边界没越界，再提交。这个小动作帮我拦下了许多毫无意义的时间浪费。

如果你把上面这些边界、体例、识别方法都过了一遍，再遇到开头那道题，应该能直接反应过来：初始全零数组，m 次区间加，最后输出数组——三行代码的事，别去写两重循环了。这就是差分的价值。