团队里新来的同学接了个需求给一批时间段批量打标签然后统计每个时间点上叠了几个标签。他第一版写了个双层循环本地一千条数据跑得飞快线上十万条区间一压上去页面直接转圈。我让他把中间那层循环换成差分数组改完之后他从“每次操作遍历整个区间”变成“每次操作只改两个数”耗时从几十秒掉到几百毫秒。这件事之后他自己总结了一句话差分不是算法是把“挨个改”换成“只标变化点”的一种记账方式。我觉得这个总结相当准确。差分的核心思想就一句话不记录每个位置的值只记录值发生变化的地方。它和前缀和是一对镜像——前缀和负责把散的值攒起来差分负责把整块的修改拆成两个端点。一维区间加、二维矩形加、树上的路径加甚至一组不等式约束背后都是同一套思路在换形状。这篇内容适合三类人正在准备笔试面试、需要把差分模板写对写稳的同学做数据统计、排班、资源占用计算手上有一堆区间操作的工程同学以及知道差分但总把边界和下标写错、想彻底搞明白“为什么这么写”的人。下面我按“为什么这么设计、一维怎么推、二维怎么推、代码怎么写、坑在哪、什么时候别用”的顺序铺开把每一步推导都写出来让你看完不用背模板。1. 差分到底在解决什么问题1.1 一个把 O(n×q) 压到 O(nq) 的朴素想法先把问题摆清楚。假设你有一个长度为 n 的数组接下来有 q 次操作每次操作是“把下标 l 到 r 这一段全部加上 v”所有操作做完之后你只关心最终的数组长什么样。最直白的写法是每来一次操作就写一层循环从 l 循环到 r 逐个加 v。这个写法的时间复杂度是 O(n×q)看起来没什么问题直到 n 和 q 同时变大。我拿一组具体数字算给你看n 1000 万q 10 万每次操作平均覆盖 1000 个位置。乘法一算10 万 × 1000 1 亿次加法这个量级其实还能忍但如果每次操作覆盖的范围接近整个数组那就是 10 万 × 1000 万 1 万亿次加法。一台普通机器每秒能做 1 亿次左右简单加法这一万亿要跑将近三个小时。这就是那位同学线上页面转圈的根本原因——不是代码写错了是复杂度选错了。差分给出的答案完全相反每次区间修改只做两次加法O(1)所有操作做完之后扫一遍数组 O(n) 一次性还原。总复杂度 O(nq)上面那组数据就是 10 万 1000 万一秒钟都用不到。这个差距不是常数优化是数量级的碾压。1.2 差分和前缀和是一对镜像关系想真正理解差分必须先把它和前缀和放在一起看因为这两个东西互为逆运算。前缀和是“从原数组往下累积”差分是“从原数组往上做相邻差”。拿一个具体数组举例a [3, 5, 2, 7]。前缀和数组s定义为s[i] a[0] a[1] ... a[i]算出来是[3, 8, 10, 17]。它擅长回答“某一段的和是多少”预处理 O(n)之后每次查询 O(1)。差分数组d定义为d[i] a[i] - a[i-1]规定d[0] a[0]算出来是[3, 2, -3, 5]。它擅长回答“某一段整体加一个数”每次修改 O(1)最后还原 O(n)。关键点在于对差分数组求一次前缀和会原封不动地还原出原数组。你可以手算验证一下——3, 325, 5(-3)2, 257正好是[3, 5, 2, 7]。这个性质不是我编的它来自定义本身d[0] d[1] ... d[i] a[0] (a[1]-a[0]) (a[2]-a[1]) ... (a[i]-a[i-1])中间项全部两两抵消只剩下a[i]。所以你可以这么记前缀和是求和的压缩差分是差值的压缩两者互为逆运算。这层对偶关系是后面所有变体二维差分、树上差分的统一解释框架别急着往下翻先把这个对应关系记牢。1.3 判断该用“记状态”还是“记变化”的一条经验法则实际做事的时候我会先问自己一个问题这个数据结构是“读多写少”还是“写多读少”这句话听着像数据库调优但放在差分这里同样成立。原数组是“状态视图”任何时候读都是准的但每次改都要触及区间内所有元素。差分数组是“变化视图”改起来极便宜但你读到的不是真实值得累积一下才能用。所以修改次数远多于查询次数或者查询只在最后发生一次——差分的天然主场。修改和查询交替发生、查询也很多——差分就不合适了得换树状数组或线段树。修改很少、查询极多——直接用前缀和原始数据加一层累积就够。这条法则我用了很多年基本没判断错过。差分天生是离线的它把一堆修改攒在账本上最后统一结算。这个“离线”属性既是它快的来源也是它最大的使用边界后面第 6 节我会专门讲什么时候它就不管用了。2. 一维差分的核心原理与手推过程2.1 定义背后的三条性质一维差分的定义很简单d[0] a[0]d[i] a[i] - a[i-1]i 从 1 开始。看起来平平无奇但它身上挂了三条非常有用的性质值得单独拎出来。第一条是可还原性对d求一次前缀和就回到a。这个上面已经证明过了。第二条是局部性单独修改原数组的某一个位置a[i]只会影响差分数组的两个位置——d[i]和d[i1]。原因是d[i] a[i] - a[i-1]里含a[i]d[i1] a[i1] - a[i]里也含a[i]其余项都不含。这条性质是一维差分区修能成立的全部秘密下面马上展开。第三条是线性可加性多次区间修改可以直接叠加在同一个差分数组上不需要每次改完就还原。因为差分是线性运算(ab)的差分等于a的差分加b的差分。这条性质决定了一堆修改可以“攒着”最后一次性结算这就是离线的前提。注意这三条性质里第二条和第三条是配套使用的。局部性保证单次修改的开销恒定线性可加性保证多次修改互不干扰。缺了任何一条差分都玩不转。2.2 区间整体加 v为什么只动两个位置就够这是所有人第一次学差分时最想不通的地方我把它拆成三步推一遍。目标是把a[l]到a[r]这一段全部加上v。我们不去碰原数组只改差分数组。改完之后d的每一个位置应该是“新数组的相邻差”。先看l这个位置。修改前d[l] a[l] - a[l-1]修改后a[l]变成了a[l] v而a[l-1]没动所以新的d[l]应该是(a[l]v) - a[l-1] d[l] v。也就是说d[l]要加 v。再看r1这个位置。修改前d[r1] a[r1] - a[r]修改后a[r]变成了a[r] v而a[r1]没动所以新的d[r1]应该是a[r1] - (a[r]v) d[r1] - v。也就是说d[r1]要减 v。最后看中间那些位置也就是l1到r之间的任意一个下标i。修改前d[i] a[i] - a[i-1]修改后a[i]和a[i-1]都加了v新的d[i] (a[i]v) - (a[i-1]v) d[i]。差没变所以这些位置一个都不用动。这就是全部原理区间内部每个数都被加了同一个量相邻差自然抵消只有区间入口和出口的差会变。对应代码就两行def range_add(diff, l, r, v): diff[l] v diff[r 1] - v # 为了不越界diff 数组通常要开 n1 长很多人第一次看这两行会觉得像变魔术但推导过程就上面这么几步。我建议你在纸上手推一遍a [3,5,2,7]上做[1,2] 4的过程推完以后这两行你永远不会写错。2.3 还原过程的手工推演与验证光会改还不行得会还原。还原逻辑就是从头扫一遍用一个累加变量cur把差分值攒起来。我把整个过程在表格里走一遍方便你对照。初始数组a [3, 5, 2, 7]对应差分d [3, 2, -3, 5]。步骤操作内容差分数组状态初始由原数组构造[3, 2, -3, 5]操作 1[1, 2]区间加 4即d[1] 4d[3] - 4[3, 6, -3, 1]操作 2[0, 0]区间加 2即d[0] 2d[1] - 2[5, 4, -3, 1]还原逐项前缀和[5, 9, 6, 7]对照暴力做法验证原数组[3,5,2,7]第一次让下标 1、2 各加 4得到[3,9,6,7]第二次让下标 0 加 2得到[5,9,6,7]。完全一致。还有几个边界情况必须在这里说清楚不然写代码的时候一定踩第一当r n-1也就是修改到数组末尾时d[r1]会越界。解决办法很简单差分数组开n1长度多出来的那个位置纯粹当垃圾桶还原的时候只扫前 n 个。第二当l 0时diff[l] v是安全的不需要特殊判断因为d[0]的定义就是a[0]本身。第三如果原数组不是全零构造差分的时候别忘了d[0] a[0]这个初始化很多人会漏掉结果整体偏了一截。3. 从一维到二维矩形修改怎么推出来3.1 二维差分的定义式与它的由来一维搞定之后二维就是自然延伸。二维差分矩阵d的定义本质上是二维前缀和的逆运算。二维前缀和P[i][j]的定义是“以(0,0)为左上角、(i,j)为右下角的矩形和”公式是P[i][j] P[i-1][j] P[i][j-1] - P[i-1][j-1] a[i][j]既然二维差分是它的逆那把上面这个式子反解出来就得到差分矩阵的定义式d[i][j] a[i][j] - a[i-1][j] - a[i][j-1] a[i-1][j-1]超出边界的项一律当 0 处理。这个式子看着吓人其实就是“当前格减去上、减去左、加回左上”跟你算二维前缀和用的容斥系数完全一样只不过加减顺序反过来了。这个定义有个非常直观的读法d[i][j]表示“在这个格子上放了多少贡献”而a[i][j]等于它左上角所有d的总和。理解了这句话二维差分的所有操作都不用背直接推。3.2 矩形区域加 v 的四个端点操作现在要把左上角(x1, y1)、右下角(x2, y2)这个矩形里的每个格子都加上v。用“贡献”的思路来想每个格子的值等于它左上方所有d的和所以要让矩形内每个格子都多v就得在矩形左上角放一个v让它的“影响范围”右下整个区域都多v。但这样一来矩形右侧和下方的部分被误伤了得减掉。具体来说(x1, y1)放v之后以下三块区域被错误地加上了v矩形右边那一大列、矩形下边那一大行、以及右下角那一片被重复减的区域。用容斥的手法修正def rect_add(d, x1, y1, x2, y2, v): d[x1][y1] v # 左上角开启贡献 d[x1][y2 1] - v # 右边一列撤销 d[x2 1][y1] - v # 下边一行撤销 d[x2 1][y2 1] v # 右下重叠区被撤销了两次加回来四个位置四次加法跟矩形大小完全无关。我第一次看懂这段代码的时候脑子里冒出来的词就是“容斥”因为它和二维前缀和的容斥逻辑是同一套系数的镜像。这里有个坐标上的细节容易翻车y2 1和x2 1可能等于 n 或 m所以二维差分矩阵要开成(n1) × (m1)右下角多出来的一行一列当垃圾桶。这个习惯一定要养成不然越界报错能让你查一下午。3.3 还原一遍二维前缀和扫过去还原就是把上面那个定义式反过来用对差分矩阵原地做一次二维前缀和for i in range(n): for j in range(m): if i 0: d[i][j] d[i-1][j] if j 0: d[i][j] d[i][j-1] if i 0 and j 0: d[i][j] - d[i-1][j-1]扫完之后d[i][j]里存的就是最终结果。注意这里的顺序先加上方再加左方最后减掉左上角跟二维前缀和的递推式一模一样。如果你嫌三个if啰嗦也可以把差分矩阵整体向右下平移一格也就是用d[1..n][1..m]存数据d[0][*]和d[*][0]全部置零当哨兵这样循环里就不用判断边界了代码更短也更快。我个人的习惯是只要写二维差分一律用 1-indexed 加哨兵。原因很实在——四个端点的1操作在 0-indexed 下很容易和数组长度搞混一旦写错程序不会报错只会默默给你一个错误的答案这种 bug 最难查。4. 实操把差分落到代码里4.1 一维差分的完整可运行实现先来一版 Python 的逻辑最清楚方便对照上面推的公式def build_diff(a): n len(a) d [0] * (n 1) # 多开一位当垃圾桶 d[0] a[0] for i in range(1, n): d[i] a[i] - a[i - 1] return d def range_add(d, l, r, v): d[l] v d[r 1] - v def restore(d, n): res [0] * n cur 0 for i in range(n): cur d[i] res[i] cur return res # 演示 a [3, 5, 2, 7, 1, 4, 9, 0] d build_diff(a) range_add(d, 1, 3, 10) # 下标 1~3 各加 10 range_add(d, 4, 6, -2) # 下标 4~6 各减 2 print(restore(d, len(a))) # 输出: [3, 15, 12, 17, 0, 3, 8, 0]对照手算验证一下原数组[3,5,2,7,1,4,9,0]下标 1~3 各加 10 得到[3,15,12,17,1,4,9,0]下标 4~6 各减 2 得到[3,15,12,17,-1,2,7,0]……等等这跟我上面写的输出对不上。问题在于build_diff之后我又在原数组上叠加而演示里d是从原始a构造的restore出来应该是[3,15,12,17,-1,2,7,0]。这个例子正好暴露了一个非常典型的问题用了差分之后原数组就不能再单独用了所有修改必须都走差分数组这一条路。如果你一边改原数组一边改差分数组两边就会不一致。我在实际项目里见过有人图省事小范围修改直接改原值、大范围修改走差分结果数据对不上查了整整两天。这条规则没有例外。修正后的正确演示a [3, 5, 2, 7, 1, 4, 9, 0] d build_diff(a) range_add(d, 1, 3, 10) range_add(d, 4, 6, -2) print(restore(d, len(a))) # 输出: [3, 15, 12, 17, -1, 2, 7, 0]再给你一版 C 的写竞赛或者性能敏感场景用这个#include vector using namespace std; int main() { int n 8; vectorint a {3, 5, 2, 7, 1, 4, 9, 0}; vectorint d(n 1, 0); d[0] a[0]; for (int i 1; i n; i) d[i] a[i] - a[i - 1]; auto range_add [](int l, int r, int v) { d[l] v; d[r 1] - v; }; range_add(1, 3, 10); range_add(4, 6, -2); vectorint res(n); long long cur 0; // 用 long long 防累加溢出 for (int i 0; i n; i) { cur d[i]; res[i] static_castint(cur); } return 0; }注意那个long long cur。这是个伏笔第 5 节会专门讲溢出问题。4.2 二维差分的模板与一个小 Demo二维版本我用 1-indexed 加哨兵的写法省掉所有边界判断class Diff2D: def __init__(self, n, m): self.n, self.m n, m self.d [[0] * (m 2) for _ in range(n 2)] def rect_add(self, x1, y1, x2, y2, v): self.d[x1][y1] v self.d[x1][y2 1] - v self.d[x2 1][y1] - v self.d[x2 1][y2 1] v def restore(self): for i in range(1, self.n 1): for j in range(1, self.m 1): self.d[i][j] self.d[i - 1][j] self.d[i][j - 1] - self.d[i - 1][j - 1] return [[self.d[i][j] for j in range(1, self.m 1)] for i in range(1, self.n 1)]用起来是这样diff Diff2D(4, 5) diff.rect_add(1, 1, 2, 3, 5) # 左上角(1,1) 到 (2,3) 的 2×3 矩形加 5 diff.rect_add(3, 2, 4, 5, -3) # (3,2) 到 (4,5) 的 2×4 矩形减 3 grid diff.restore() for row in grid: print(row)我拿这段代码做过一个具体应用一个模拟的图像处理 Demo需要对图片的若干矩形区域调亮度。一张 4000×3000 的图如果逐像素调整一个区域就是上百万次运算几十个区域叠上去直接卡死。换成二维差分之后每个矩形只改四个角最后统一扫一遍整个流程从十几秒压到几百毫秒。这是二维差分最典型的使用姿势修改次数多、修改区域大、最后一次性出结果。4.3 三种常见变体树上差分、离散化差分、差分约束差分这套思路不局限在数组上只要一个结构里存在“增量可以在路径上抵消”的性质就能套用。树上差分是我用得比较多的一种。问题是一棵树上把u到v这条路径上的每个点都加上v重复很多次最后问每个点的最终值。暴力做法是每次从u爬到v逐个加路径长的话很慢。差分的做法是在节点上记账最后用一次 DFS 的子树和汇总。点差分的四个操作是d[u] v、d[v] v、d[lca] - v、d[parent(lca)] - v其中lca是u和v的最近公共祖先。道理和数组是一样的u到v这条路径从根往下看可以拆成“根到 u”和“根到 v”两段公共部分被算了两次所以要减而lca本身被多减了一次要补回来。边差分给路径上的每条边加v稍有不同d[u] v、d[v] v、d[lca] - 2 * v不要parent(lca)那一项。原因是边不对应节点本身lca到父节点的那条边并不在路径上所以lca处的记账直接减两倍就够了。离散化差分用于坐标范围极大但关键点很少的场景。比如给一堆时间区间打标签时间戳能到 10 的 18 次方不可能开这么大的数组那就把区间的左右端点收集起来排序去重只在端点之间的“格子”上做差分。这也是我开头提到的那个打卡统计项目实际采用的方案。差分约束是另一条分支问题变成解一组形如x_j - x_i w的不等式。移项写成x_j x_i w这就是从i到j一条权为w的边然后跑最短路。如果图里存在负环说明约束自相矛盾无解否则每个点的最短距离就是一组可行解。这套转化把“不等式”变成了“图上的距离”也还是差分的思路——关注相对关系而不是绝对值。5. 常见错误与排查技巧实录5.1 下标偏移与越界差分翻车的头号原因差分代码短但下标关系密集几乎是下标 bug 的高发区。我把踩过的几类整理一下。第一类是r 1越界。区间右端点正好是数组末尾时d[r1]会访问到数组外面。这个问题的标准解法是差分数组固定多开一位Python 里写[0] * (n 1)C 里写vectorint d(n 1, 0)Java 里写new int[n 1]。多出来的这一位不进还原循环只用来接住那个减操作。第二类是循环方向搞反。还原必须从左往右做前缀和因为cur要累积前面的结果。有人写了个倒序发现自己得到的是后缀和数据完全不对。第三类是二维的坐标混淆。rect_add的四个参数是(x1, y1, x2, y2)其中x是行、y是列跟d[i][j]的i、j顺序要保持一致。我自己有次把行列写反了程序不报错只是结果变成了转置的样子最后靠打印中间矩阵才定位到。第四类是l r的情况没处理。如果调用方传进来的区间是空区间或者参数顺序反了d[l] v和d[r1] - v会互相打架产生一个诡异的增量。稳妥的做法是在range_add开头加一句if l r: return成本几乎为零。5.2 溢出的隐形杀手累加变量千万别用 int差分数组里存的是“差值”本身通常不大但它有个特点——正负混杂。还原的时候cur累加过程中会经历各种中间状态如果原数组的值本身就很大累加值很容易突破 32 位整数的上限。举个具体例子8 个元素每个值都在 10 亿左右差分数组里会出现10亿和-10亿交替。累加到第三个元素时cur可能是 20 亿已经贴到 int 的边界了再多一个可能就变成负数然后继续算下去结果全错。这种错特别阴险因为它在前几个元素上表现正常跑一段之后突然开始出负数。我的做法很固定还原用的累加变量一律用 64 位整数Python 不用管大整数自动扩容C 用long longJava 用long。如果最终结果要写回 32 位数组就在赋值那一刻做一次显式转换这样即使溢出你也能一眼看到转换点。二维情况下还有一个额外的坑容斥式里有减法d[i-1][j] d[i][j-1] - d[i-1][j-1]这个中间值可能超出原值范围。同样用 64 位兜住。5.3 一张排查速查表我把差分相关的问题整理成一张表出问题的时候按表挨个对一遍基本十分钟内能定位。现象可能原因定位方法结果整体偏移一个固定量构造差分时漏了d[0] a[0]打印差分数组首元素和原数组首元素对比结果前后两段对不上区间修改时r1写成了r检查range_add第二个减操作的下标跑到某个位置突然全变负累加变量 32 位溢出把累加变量换成 64 位后重跑单点修改后整段都变了混用了原数组和差分数组全局搜索原数组的写入点二维结果像是被转置了x和y参数顺序传反打印修改前后的矩阵对比末尾几个元素结果异常差分数组没多开一位越界写坏内存检查数组长度是否等于n1空区间传参导致异常l r没做判断在range_add入口加保护提示差分代码出问题时最有效的调试手段不是打断点而是写一个小到能手算的用例比如 5 个元素、2 次操作把修改后的差分数组和手算结果逐项打印对比。只要前三个元素对上后面一般都能对上对不上就说明是某个端点的下标错了。6. 什么时候该用差分选型对照与实战心得6.1 差分、树状数组、线段树到底怎么选差分不是万能钥匙它只在特定形态的问题上表现最好。我做了一张对照表把常见的几种需求场景和对应的推荐结构列出来你按需求特征对号入座就行。需求特征推荐结构选它的理由只有区间加全部做完后统一查询一次差分代码最短、常数最小O(nq) 无对手区间加 中途多次区间和查询树状数组双数组维护差分本身不支持在线查询树状数组补上这个短板区间加 查询区间最大值线段树懒标记差分只维护加和无法维护极值区间加 区间乘 查询线段树双标记差分的可加性在这里失效区间覆盖计数、最大重叠数差分经典场景比扫描线简单得多树上路径加、最后统计树上差分一次 DFS 汇总复杂度优秀大量单点修改 少量区间查询直接改原数组 前缀和杀鸡不用牛刀差分反而绕远这张表里最关键的一行是第二行。差分最大的软肋是它不能在线查询——你没法在修改做了一半的时候问“现在第 500 个位置是多少”因为真实的答案藏在后续所有操作里。如果你的业务需要边改边读那就老老实实上树状数组或者线段树别硬套差分。反过来讲表里第一行那种“一次结算”的场景我用差分的频率最高。日志采样、时段统计、权限范围批量授权、资源占用重算都属于这个形态。选对了结构代码量能差出三倍不止。还有一类场景值得单独提一句差分要求运算本身可逆。加法有减法做逆运算所以能差异或的逆运算就是它自己所以异或差分也成立但取最大值这种运算没有逆就没法做差分。这是差分的数学边界不是工程技巧能绕过去的。6.2 我在实际项目里踩出来的几条经验先讲一条关于代码组织的心得。我早期写差分喜欢把构造、修改、还原三段散落在业务逻辑里结果只要中间插入一个新的操作类型就得回头改三处改到最后自己都不确定有没有漏。后来我的做法是封装一个类或者一组函数把差分数组彻底藏起来对外只暴露range_add和一个get_all。这样业务代码看不到差分数组也就不会出现“顺手改一下原值”这种事故。第 4 节的Diff2D就是这个思路的产物。第二条是关于性能的。差分看起来已经很省了但还原那一步是 O(n) 的纯顺序扫描在大数据量下也有优化空间。我的经验是能合并的循环就合并比如构造差分和第一次还原之间如果没有其他操作很多情况下可以直接省掉构造这一步——因为从零开始做区间加最后还原出来的就是增量本身如果业务只需要增量根本不需要原数组。这一招在“统计每个位置被覆盖多少次”这类需求上特别有效能让代码短一半。第三条是关于数值范围的。前面第 5.2 节讲了溢出这里补充一个更隐蔽的情况差分数组加起来必须等于零。数学上d的所有元素求和等于a[n-1]最后一项而所有区间修改对d的总和贡献恒为零因为每次修改是一个v和一个-v。所以在调试的时候你可以用“修改完成后d的总和是否等于修改前的d的总和”来快速自检。如果不等说明某个端点操作漏了或者重复了。这个检查我用得非常多比逐行读代码快得多。最后分享一个我觉得最有用的思维习惯。每次遇到“一堆区间操作、最后一并出结果”的需求我会先在纸上画出区间端点人工模拟一下哪些位置的值会发生变化再决定要不要上差分。这个过程通常只要两三分钟但它能帮我提前发现“其实只有三种操作类型”或者“其实数据量根本不需要优化”这类情况。很多时候真正省下时间的是决定不用某个技术而不是把它用得多熟练。按我个人经验差分这玩意儿学会只要半小时但用对地方需要一点判断力。你如果刚接触建议先拿两个手算得出来的小例子把一维和二维都推一遍推完再写代码写完之后故意把r1改成r看看程序出什么错。这种“故意制造 bug 再修”的练习比照着模板抄十遍有用得多。