前阵子我在本地的模拟项目里处理一批区间统一加值的需求数据量从几千条涨到几十万条之后原来的逐项遍历写法直接跑不动。一次区间修改是 O(n)操作一多整体时间就完全失控。后来我换成差分算法cpp区间修改从 O(n) 降成 O(1)整批操作加最终查询的总耗时降到毫秒级。那之后我就把差分数组当成了一个默认的“第一反应方案”凡是看到“多次区间统一修改 最后统一查询”的组合我基本都先往差分上想。这篇文章不打算从概念定义开始念书而是按照我实际用过一遍的顺序来写先解释差分数组为什么能这么快再给出可以直接抄的一维、二维 C 实现然后把它和树状数组、线段树做一次面对面的对比最后把我踩过的坑和自用的调试方法整理出来。不管你是刚接触数据结构的初学者还是在比赛或工程里被区间操作卡过耗时的开发者这篇内容都应该能让你少走一段弯路。1. 差分算法的本质把“改一段”变成“改两点”1.1 为什么逐点更新会慢差分的思路又是什么假设现在有一个数组a[1..n]要对区间[l, r]统一加上一个值x。最朴素的做法就是写一个循环从l走到r逐个执行a[i] x。每个区间操作的时间是 O(r-l1)最坏就是 O(n)。如果后面还要做很多次操作复杂度直接乘上去几十万的数据配合几十万次操作基本就是上亿次循环跑起来非常难受。差分的核心思路是一个很反直觉的转换我们不直接记录数组每个位置“是多少”而是记录每个位置“相对前一个位置变化了多少”。这个相对变化量的数组就是差分数组。数组里的大部分相邻元素本来就是相同的只有区间两端位置会因为一次区间加而发生变化。所以一次区间加在差分数组上只需要修改两个位置左端点l加x右端点后面的r1减x。中间的每个元素和它前一个元素的相对差值没有变化自然不用动。想通这一层之后我建议你直接抛弃“区间加就是遍历数组”的直觉。区间加的本质不是“每个点都变了”而是“这一段相对前后整体抬高了”。整体抬高只需要记录抬高的起点和结束点差分数组正好就是干这个的。1.2 前缀和是还原钥匙两组公式一次记牢差分数组的定义很简单d[1] a[1] d[i] a[i] - a[i-1] (2 i n)反过来原数组可以由差分数组的前缀和得到a[i] d[1] d[2] ... d[i]这个还原关系是整篇内容最关键的地方。差分数组本身不是最终结果它只是“操作记录”真正要拿到值必须做一遍前缀和。我见过不少初学者把差分数组输出出来然后疑惑为什么“原数组没有变”其实就是忘了前缀和这一步。为什么区间加只改d[l]和d[r1]可以从还原公式来理解。前缀和就像一条坡道差分数组里的每个非零值就是这条坡道上的一个台阶。在l位置加一个x意味着从l开始所有后续的前缀和结果都会变大x为了不影响到r1及之后的位置需要在r1位置减一个x把这个台阶重新压平。这样真正变大的区间只有[l, r]。这个“先加后减”的模式在二维乃至更高维的差分里还会继续出现只是变成多个位置组合操作。理解了一维的变化量思想后面推广起来就自然了。2. C 实现细节从接口设计到边界处理2.1 一维差分基础模板三块核心代码直接抄我一般在 C 里用 1-indexed 数组也就是下标从 1 开始这样区间边界l, r的表达和题目描述一致不容易弄混。数组大小至少分配成n 2因为区间右端点是n时我们要修改d[n1]少了这个位置就会越界。从一个原始数组a[1..n]构造差分数组的代码#include bits/stdc.h using namespace std; using ll long long; vectorll buildDiff(const vectorll a) { int n (int)a.size() - 1; // a[0] 占位实际数据从 1 开始 vectorll d(n 2, 0); for (int i 1; i n; i) { d[i] a[i] - a[i - 1]; } return d; }之后所有的区间加都在这一个数组上操作不需要碰原数组void rangeAdd(vectorll d, int l, int r, ll x) { d[l] x; d[r 1] - x; }最后需要还原出真实值的时候做一遍前缀和void applyDiff(const vectorll d, vectorll a) { int n (int)a.size() - 1; ll sum 0; for (int i 1; i n; i) { sum d[i]; a[i] sum; } }整个流程就是buildDiff构造初始差分多次rangeAdd记录操作最后applyDiff统一还原。中间不再碰原数组直到最后一步才把结果“算出来”。2.2 复杂度与内存先算清账再决定用不用一维差分做一次区间修改是 O(1)最终还原一次是 O(n)假设有 m 次区间修改整批操作的总复杂度就是 O(n m)。比起朴素做法 O(n * m) 的复杂度这个下降是降维打击级的。内存方面也很省只需要一个长度n 2的数组。如果原来的a数组还需要保留那你就同时持有原数组和差分数组两份数据空间是 O(n)。其实大多数场景下a的初始值可以直接参与构造差分后面的修改全部记录在d上最后再把d的前缀和写回a不需要额外维护一份“中间结果”。我自己的经验是当操作次数 m 和数组长度 n 都来到十万这个级别时差分就是比遍历好得多的方案。但要注意差分适合的是“先全部操作完再统一查询”的离线场景。如果你每做一次区间加立刻就要知道某个位置的值纯差分数组并不合适因为每次查询都重做前缀和的话代价反而更大。这种在线场景应该用后面会提到的树状数组或者线段树来配合。2.3 初学者的三个典型错误我当初也各踩过一次第一个错误是数组长度不够r n时去操作d[r1]结果越界。这个问题很隐蔽因为小数据可能碰巧不出错或者只是修改到了相邻内存程序没立刻崩。解决办法很简单所有差分数组统一开n 2而不是n 1给自己留出那个“哨兵位”。第二个错误是把差分数组和原数组混着用。有人会在做了一部分区间加操作后突然把a数组里的值打出来看发现数值完全不对。这是正常的因为此时差分还没还原。记住一点操作阶段的唯一真相来源是da只是最终输出用的容器。第三个错误是多次还原。我曾经在一个循环里调用applyDiff多次每次把前缀和累加到原数组上导致数值翻倍错误。正确做法是只还原一次如果后面又有新的区间操作要重新从当前还原结果构造差分数组或者保持差分数组不还原继续记录新的操作。3. 二维差分给矩阵子块统一加值的高效扩展3.1 二维差分怎么构造从“一维台阶”到“二维叠加”一维学会了二维并不算新知识本质就是在一维思想外面再套一层。定义二维差分数组d[i][j]使得原矩阵a[i][j]等于左上角(1,1)到(i,j)这个矩形区域的所有差分值之和a[i][j] sum_{x1..i} sum_{y1..j} d[x][y]也就是对差分数组做二维前缀和能还原出原矩阵。构造方式可以直接类比一维对原矩阵初始化一个全零的d然后对每个位置(i,j)把a[i][j]当成从(i,j)到(i,j)的单点区间加用一次单点修改来表示。不过更常见的做法是直接从原矩阵的相邻差来构造vectorvectorll buildDiff2D(const vectorvectorll a, int n, int m) { vectorvectorll d(n 2, vectorll(m 2, 0)); for (int i 1; i n; i) { for (int j 1; j m; j) { d[i][j] a[i][j] - a[i-1][j] - a[i][j-1] a[i-1][j-1]; } } return d; }这个公式和有 DP 前缀和的转移正好反过来。因为a[i][j]本身就是差分数组的一个矩形前缀和解这个二维前缀和方程就得到上面的构造式。3.2 子矩阵统一加值四个位置一次搞定对原矩阵上从(x1, y1)到(x2, y2)的子矩形统一加v在差分数组上只需要改四个位置void rangeAdd2D(vectorvectorll d, int x1, int y1, int x2, int y2, ll v) { d[x1][y1] v; d[x2 1][y1] - v; d[x1][y2 1] - v; d[x2 1][y2 1] v; }为什么是这四个位置你可以把它拆成两个维度的组合在x方向看矩形在x1处开启在x21处关闭在y方向看矩形在y1处开启在y21处关闭。四个组合就是“开开、关开、开关、关关”对应加上、减去、再减去、再加上利用容斥把重叠修正掉。还原时同样做二维前缀和void applyDiff2D(vectorvectorll d, int n, int m) { for (int i 1; i n; i) { for (int j 1; j m; j) { d[i][j] d[i-1][j] d[i][j-1] - d[i-1][j-1]; } } }还原之后d[i][j]里存的就是最终矩阵的数值。这里我直接在原差分数组上原地前缀和省一个矩阵空间。如果你需要在还原后用原数组继续做别的操作就先拷贝一份再还原。3.3 从二维到多阶差分思想的通用模式实际上把一维扩展到二维背后是一个通用规律在一维区间加需要 2 个端点在二维矩形加需要 2 的平方也就是 4 个角点在三维立方体加需要 2 的三次方也就是 8 个角点。n 维的区域统一加值对应到 n 维差分数组上就是修改 2 的 n 次方个顶点每个顶点的符号由容斥原理决定。这个模式在图像处理里也很有用。比如给某个矩形区域的像素统一增加亮度本质就是子矩阵加值批量处理多块区域后最后再统一扫描还原比逐像素修改快很多。我自己在某个图像处理 Demo 里就用二维差分给 ROI 区域批量调亮度几百个矩形框叠加后只对整张图做一次前缀和速度非常直观。三维差分在实际算法题里偶尔会遇到比如“给一个三维空间中的某个长方体统一增加值最后查询整个空间的状态”。思路完全一致只是代码需要维护 8 个位置。初学者不必背诵那 8 个位置只要遇到这种题时顺手用容斥从二维推导一遍即可。4. 差分数组、树状数组、线段树怎么选一道题里的权衡4.1 一张表格看清四种方案的差异很多人学完差分数组之后会疑惑既然区间操作这么常见是不是以后都用差分就行答案是不行。差分数组的强项是“离线批量操作 最终查询”一旦变成在线实时查询或者要在区间修改之外还做复杂的区间聚合就需要别的数据结构来兜底。我把常见方案整理成一个表格方案区间修改单点查询区间查询实现复杂度典型场景朴素数组遍历O(n)O(1)O(n)极低小数据、调试纯差分数组O(1)O(n)需前缀和预计算后 O(1)低多次离线区间加最后统一查询差分 树状数组O(log n)O(log n)O(log n)中在线区间加、区间和查询线段树懒标记O(log n)O(log n)O(log n)高动态区间操作 最大值/最小值等聚合纯差分数组的“单点查询 O(n)”看着很吓人但如果你只查询一次O(n) 的总代价完全可以接受。换句话说m 次修改加一次最终查询的总复杂度是 O(m n)这非常好如果每次修改后都非要查一次总复杂度就成了 O(m n * m)反而比朴素还差因为前缀和把之前的工作全部重做了一遍。所以选型问题不是“哪个更先进”而是“你的操作顺序到底长什么样”。这也是我反复跟人强调的一点数据结构没有绝对优劣只有匹配不匹配你的使用模式。4.2 使用场景判断看到一个需求先问三个问题我在拿到一个区间操作类的需求时基本会按顺序问自己三个问题第一操作和查询是否是交替出现的如果是经典的“一边修改、一边查询”纯差分数组直接出局优先考虑树状数组或线段树。第二查询的是单点值还是区间聚合信息如果只查单点值那么差分 树状数组是最经济的选择。做法是仍然用差分数组的思想只是用树状数组来维护差分值每次区间加还是l和r1两个位置更新单点查询就是对差分做一次前缀和这两个操作都在树状数组上完成O(log n)。第三需要聚合最大值、最小值吗差分数组只能维护“值本身”的区间变化它不存储区间内部的结构信息。如果查询里要带上“区间最大值”“区间最大连续和”这种聚合内容那就老老实实上线段树。4.3 差分作为基础组件不只是个独立解法差分数组除了独立使用也经常作为更复杂数据结构的一部分。树状数组维护区间加、单点查询的时候内部维护的其实就是差分数组只是用树状数组加速了前缀和的实时查询。一些离线问题的解法流程也常见“差分记录事件 扫描线结算”的模式比如先按时间顺序记录每个事件在当前时刻的影响端点再一遍扫描累计结果。这意味着你在工程里可以把差分数组当作一个“事件记录表”不一定要还原到原数组。举个例子要统计某段时间内同时活跃的会话数可以把每个会话的开始时间l记1结束时间r1记-1最后按时间扫描一遍累计值就是在该时刻活跃的会话数。这就是差分思想在真实业务里的典型应用跟数组区间加完全共用一套逻辑。5. 实测踩坑记录与自用调试方法5.1 逻辑误区在还原之前就查询得到的是差分值不是真实值这个坑我印象最深。有一回我在某段业务逻辑里构造完差分数组统计某一小块区间的数据总量结果怎么都不对。排查半天发现自己是直接对差分数组做区间求和而不是先还原成原数组再求值。差分数组的区间和没有直观意义必须前缀和还原之后原数组本身才是一个个真实的值。如果你想一边修改一边查询却仍然希望利用差分的效率正确姿势是用树状数组维护差分数组。每次区间加仍然是两个单点修改单点查询做一次前缀和如果还要区间求和则用两个树状数组分别维护差分值和差分值乘下标这些是树状数组的进阶内容。初学者只要记住纯差分数组不适合中间查询这个问题就不会再犯。5.2 数值溢出与取模不是简单地把 int 换成 long long 就结束差分数组里存的是变化量通常带有正负号。区间加次数多、单次值又大的时候d[r1]可能累积成一个绝对值非常大的负数在还原过程中又会被前缀和慢慢拉回正常范围。这个中间过程的数值可能远超最终结果用int经常因为溢出之后先变成正数再逐渐抵消结果一团糟。我的习惯是看到 ai bj 这类数值范围不确定的题第一反应就是using ll long long。如果题目带取模需要注意负数取模的问题。更稳妥的写法是void rangeAddMod(vectorll d, int l, int r, ll x, ll MOD) { d[l] (d[l] x) % MOD; d[r 1] (d[r 1] - x % MOD MOD) % MOD; }还原时也每步取模最后把结果统一(sum MOD) % MOD归正。不要小看这一步比赛环境里输出差一个正负号就是 WA。5.3 调试技巧小样例手算 验证差分数组的“成对性”差分数组的调试其实比普通数组更直观因为它有个很好的特征所有非零位置的值可以按区间端点成对出现。对一维差分数组来说任何一次合法的区间加都会在数组里留下一个“加 x”和一个“减 x”所以所有非零项相加应该等于零也就是差分数组的总和恒为 0。如果你自己加完操作之后把d数组求和发现不是 0那几乎可以肯定某个区间操作的l或r1写错了。二维差分也有对应的验证方式对一次矩形加四个角上的值求和也应该是 0。遇到结果不对的时候可以先清零差分数组只跑一次简单的矩形加然后手算前缀和检查矩阵四个角的数值是否符合预期。这个验证我称为“最小复现法”比直接跑大数据集找错高效得多。另外一个小技巧是造“全零差分”起始状态。很多题目的初始数组是全 0这种情况连buildDiff都省了直接全零开刷。调试时配合一组标答数据把差分中间值打印出来人工对照通常问题一眼就暴露了。我自己调试差分相关代码的习惯是先写一个debugPrint函数把d数组打出来再手动算一遍前缀和写在纸上逐项核对。虽然麻烦但几次之后你就会对“差分值长什么样、还原后应该是什么样”建立很强的直觉后面写代码出错的概率会直线下降。最后再分享一个小技巧。差分数组里的非零位置本质上是这个序列所有“变化点”的位置。分析问题时可以把差分数组做成一个只含变化点的事件列表然后用扫描线处理。这个思路不光在算法题里好用在业务数据分析里也很实用凡是涉及到“某个区段统一生效/失效”的模型差分数组基本都能派上用场。如果你有类似的场景建议自己动手试一次一维和二维的差分流程跑通之后这套工具以后就是你的常规选项了。