差分这个东西我第一次接触时是在一道区间加、单点查询的题上当时用线段树硬写写了八十多行还调了半天标记下推。后来有位做题很猛的朋友看了一眼说这题差分十行就完了。那一刻的感受挺复杂——不是不会是没想到还能这么想。差分原理本身不复杂难的是在什么场景下能想到用它以及边界到底该怎么算。这篇就把差分从小到大拆一遍从一维差分数组的构造与还原到二维差分矩形的四次加减再到树上差分和差分约束这类进阶玩法最后把我这些年踩过的坑摆出来。适合刚学完前缀和、想找一个更省事的区间操作思路的同学也适合写了几年代码但对“差分”只停留在背模板层面的朋友。1. 差分到底是什么从一道刷墙题说起1.1 走廊刷墙差分最朴素的样子假设有一条很长的走廊墙上贴着 1000 块瓷砖编号 1 到 1000。现在有三批工人来刷漆第一批刷第 100 到第 300 块第二批刷第 250 到第 600 块第三批刷第 500 到第 900 块。问最后每块瓷砖被刷了几次。最直接的做法是每来一批工人就从起点到终点挨个加一。三批工人加起来总操作量大概是 200 350 400 950 次。这个量级还能接受但如果瓷砖有一百万块、工人有十万批呢每次操作平均覆盖一半区间总量就是五千万次虽然勉强能跑但已经很不舒服了。换个思路想我不记录每块砖被刷了几次我只记录**“从哪一块开始多了从哪一块开始少了”**。第一批工人来我在第 100 块的位置记一个“1”在第 301 块的位置记一个“-1”。意思是从 100 开始刷漆次数比前面多 1从 301 开始又回到原来的水平。三批工人都这么记最后我只需要从第 1 块走到第 1000 块一路累加这些“变化量”就能还原出每块砖的实际次数。三批工人只产生 6 次记录操作。这就是差分的全部精髓把一次区间修改压缩成两次单点修改。这个“走廊刷墙”的模型看着像小孩过家家但它对应的实际场景非常多某段时间内的并发请求计数、某个温度区间内的采样点累加、某段里程内的费用叠加、游戏里某个坐标范围内的伤害区域判定。凡是“区间统一加一个值最后一次性统计”的需求差分都是第一顺位要考虑的工具。1.2 差分与前缀和是一对逆运算很多人学差分时会觉得它和前缀和有点像确实如此而且这个关系值得说透因为它是后面所有推导的地基。前缀和做的事是给一个数组a构造一个数组s满足s[i] a[1] a[2] ... a[i]。也就是把“累加”这个动作提前算好之后任意区间和都能用s[r] - s[l-1]一次减法拿到。差分做的事正好反过来给一个数组a构造一个数组d满足d[i] a[i] - a[i-1]约定a[0] 0。也就是把“相邻差”显式存下来。两者的关系可以用一句话概括对差分数组求前缀和就还原出原数组对原数组求差分就得到差分数组。这两个操作互为逆运算就像加密和解密。这个逆运算关系解释了一个很关键的疑问为什么区间更新时是d[l] v和d[r1] - v因为还原的时候要做前缀和d[l]加上v之后从l开始往后的所有位置在累加时都会多算一个v为了让它只影响到r为止必须在r1处把这个v抵消掉也就是减去v。理解了这个“抵消”的动机就不需要死记公式了。顺便说一句这个思路可以一直往上叠前缀和的前缀和、差分再差分。二维前缀和的逆运算就是二维差分树上路径和的逆运算就是树上差分。套路是同一个套路只是维度变了。1.3 同名不同物几个容易混淆的“差分”这里得插一段辨析因为“差分”这个词在不同领域指的东西差别很大搜资料的时候很容易撞车。领域“差分”指什么核心用途算法/数据结构相邻元素的差构成的数组把区间修改降为单点修改信号与电子两根线上传输幅度相反、相位互补的信号抵消共模干扰提升传输质量数值计算用差分近似导数如f(x) ≈ (f(xh)-f(x))/h解微分方程、数值仿真优化算法差分演化算法用个体间差分向量做变异连续空间的全局搜索定位技术差分定位用基准站修正流动站误差提高定位精度它们共同的哲学其实是同一个不直接处理绝对值而处理“相对变化”。绝对值携带的信息多但也更“重”变化量更轻、更容易被压缩和传递。这个视角在你做任何性能优化的时候都用得上——系统里真正需要传的往往不是全量数据而是增量。不过往下走重心还是放在算法层面的一维差分、二维差分和树上差分上其他几个只是帮你建立“差分是一种通用思维”的直觉不至于看到标题就只想到一个数组。2. 一维差分数组的构造、更新与还原2.1 构造一次遍历就能搞定一维差分数组的构造非常轻一趟循环就完事。用 Python 写出来大概是这样def build_diff(a): n len(a) d [0] * (n 2) # 多开两位给 r1 留空间 for i in range(1, n 1): d[i] a[i] - a[i - 1] # a[0] 约定为 0 return d这段代码里有几个细节值得掰开说。第一下标从 1 开始。这是竞赛和工程里都很常见的约定好处是a[i-1]不会越界d[r1]也天然合法。代价是数组要开n2大小不能用 0 下标直接对应原始数据。如果你更喜欢 0 下标也能写公式变成d[i] a[i] - a[i-1]i0、d[0] a[0]更新时变成d[l] v、d[r1] - v只是r1有可能等于n需要在数组尾部补一位。两种写法都对但一个项目里最好统一一种混着用是低级 bug 的温床。第二d的初值不需要真的从a构造。如果题目的初始数组全为 0只做区间加操作那么d直接全零初始化即可最后统一前缀和还原。只有当原始数组非零、并且需要在它基础上继续做区间修改时才需要先构造差分。这一点很多人会绕进去明明可以直接在差分数组上累加a的影响却非要把a整体构造一遍白白多写一段代码。换一种更省事的等价写法把“给a[i]赋初值”也看成一次“区间[i, i]加上a[i]”的操作那么所有初始化都统一成区间加代码路径就只有一个不容易漏。2.2 区间更新为什么只动两个位置区间[l, r]整体加v核心就两行def range_add(d, l, r, v): d[l] v d[r 1] - v为什么是这两行前面用“抵消”解释过了这里再从另一个角度看一遍差分数组的每一项d[i]表示“第i个位置相对于第i-1个位置的变化量”。给[l, r]全体加v等于在l处凭空多出一个台阶相对前一位增加了v在r1处这个台阶得落回去相对前一位减少了v。区间内部的相邻关系没有变所以内部的差分值一个都不用动。这个“只有台阶的两端会变”的直觉很重要它直接推广到了二维二维差分修改一个矩形只影响矩形的四个角点因为矩形内部相邻的差分关系同样不变。还原过程就是一次前缀和def restore(d, n): a [0] * (n 2) cur 0 for i in range(1, n 1): cur d[i] a[i] cur return a注意这里的cur是滚动累加的不需要额外开一个前缀和数组。如果只需要最终结果、不需要保留中间态这个写法能省一半内存。复杂度账本很清楚构造O(n)每次区间修改O(1)最后一次还原O(n)。总共m次修改的话总复杂度O(n m)。对比暴力的O(n*m)当n和m都在十万量级时差距是十个数量级——这不是优化这是换了一个问题。2.3 边界与数组开多大才不越界差分代码写挂十次里有七次是数组开小了。d[r1] - v里的r1有可能等于n1如果d只开了n长度这里直接越界。Python 里会抛异常C 里是未定义行为可能不报错但结果莫名其妙。稳妥的写法是统一开n2多出来的两位一位给r1用一位给可能的哨兵用。如果你的更新范围是从 0 开始的下标还要再多考虑一位。宁可多开两个int也不要为了省内存留隐患。另一个容易忽视的边界是空区间。如果l r这两行代码会做出很奇怪的事d[l] v在r1之后等于在一个不存在的位置加了个值前缀和还原时这个值会一直影响到数组末尾结果全错。正常逻辑下不该出现l r但如果区间是算出来的比如两个坐标取交一定要在更新前加一句判断。还有一种是区间端点超出数据范围。比如坐标压缩之后算出来的r1大于实际元素个数这时候减操作落在了一个永远不会被访问的位置看起来“没生效”实际是生效了但你没还原到那里。这类问题的排查方式是输出整个差分数组看看有没有哪一位的绝对值大得离谱。提示写完差分代码第一件事是打印整个d数组。差分数组的绝对值通常都很小就是相邻差如果出现一个很大的数说明某次更新加错了位置或者漏了抵消。2.4 适用条件什么时候差分不管用差分不是万能的它有明确的适用边界越界使用会很难受。第一条只适合离线场景。差分的前提是“先把所有修改攒着最后一次性还原”。如果题目要求每次修改之后立刻查询当前状态差分就无能为力了因为还原一次就是O(n)m次查询就退化成O(n*m)。这种在线查询的场景要用线段树、树状数组或者分块。第二条只适合可减的运算。差分依赖“加进去再减出来”这个抵消机制本质上是加法群的逆元。如果运算是取最大值、取最小值、按位与这类没有逆元的操作差分就不成立。这个限制在二维和树上同样存在。第三条修改的值必须与位置无关。区间加一个常数v差分很自然。但如果区间加的是“下标乘v”或者“下标平方乘v”那就不是一阶差分能解决的了需要用到二阶差分或者把式子拆成几项分别维护。这类题在进阶训练里不少见思路是把待维护的量拆成“常数项 下标项 下标平方项”每一项单独开一个差分数组。第四条离散性问题。差分天然处理的是连续整数下标。如果数据是稀疏的、坐标跨度极大比如坐标值到 10 的 9 次方直接开数组会爆内存必须先离散化。离散化之后再差分要注意“区间”在离散化后是否还连续——如果两个相邻离散点之间有大段空隙直接把它们当作相邻来处理可能改变语义。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]是因为左上角的块被加了两次要容斥掉一次。差分数组d定义为s的逆运算把上式移项就得到d[i][j] a[i][j] - a[i-1][j] - a[i][j-1] a[i-1][j-1]这就是二维差分的构造式。它的含义是d[i][j]表示(i,j)这个位置相对于它左边、上边、左上三个邻居的“综合变化量”。还原的时候反过来把a换成用d表达a[i][j] d[i][j] a[i-1][j] a[i][j-1] - a[i-1][j-1]看这个式子和前缀和的递推式长得一模一样这就是“逆运算”的具体体现。写代码的时候还原函数和前缀和函数几乎是同一份代码只是入参不同。3.2 四个角的符号规律与代码给矩形(x1,y1)到(x2,y2)整体加v四行代码def rect_add(d, x1, y1, x2, y2, v): d[x1][y1] v d[x2 1][y1] - v d[x1][y2 1] - v d[x2 1][y2 1] v四个角的符号是 - - 。这个规律怎么记我用的是一个“投影”的思路(x1,y1)是矩形的起点从这里开始“生效”所以是v。(x21,y1)是矩形的下边界外侧从这一行开始“下面不该再受这个v影响”所以-v。(x1,y21)同理是右边界外侧-v。(x21,y21)是右下角外侧这个位置在还原时被前两个减号“减了两次”多减了所以要补回来一次v。这个解释和二维前缀和里的容斥是完全对称的前缀和是“加了两次要减一次”差分是“减了两次要加一次”。记住其中一个另一个自然就出来了。完整的验证代码可以这样写def solve(n, m, ops): d [[0] * (m 2) for _ in range(n 2)] for x1, y1, x2, y2, v in ops: d[x1][y1] v d[x2 1][y1] - v d[x1][y2 1] - v d[x2 1][y2 1] v for i in range(1, n 1): for j in range(1, m 1): d[i][j] d[i - 1][j] d[i][j - 1] - d[i - 1][j - 1] return d原地还原直接把d变成结果矩阵省一个数组。这个写法有个前提d[i][j]在累加之前保存的是差分值累加之后变成真实值两者共用一块内存。只要还原的方向是从左上到右下就不会出现“还没用完就被覆盖”的问题因为d[i][j]只会被它左边、上边、左上用过一次。3.3 小数据暴力对拍验证二维差分的边界比一维更容易出错x21和y21都可能等于n1或m1数组必须开(n2) × (m2)。我一般会在写完差分解法之后立刻写一个暴力版本对拍不超过二十行import random def brute(n, m, ops): a [[0] * (m 1) for _ in range(n 1)] for x1, y1, x2, y2, v in ops: for i in range(x1, x2 1): for j in range(y1, y2 1): a[i][j] v return a for _ in range(500): n, m random.randint(1, 6), random.randint(1, 6) ops [] for _ in range(random.randint(1, 5)): x1 random.randint(1, n) x2 random.randint(x1, n) y1 random.randint(1, m) y2 random.randint(y1, m) ops.append((x1, y1, x2, y2, random.randint(-5, 5))) fast solve(n, m, ops) slow brute(n, m, ops) for i in range(1, n 1): for j in range(1, m 1): assert fast[i][j] slow[i][j], (n, m, ops, i, j)这套对拍我几乎每写一次二维差分都会跑一遍因为二维差分的错误往往不会在大数据上暴露只在小数据的某个边角上错一格。对拍规模控制在 6 以内五百组随机用例跑起来不到一秒性价比极高。另外提一句对拍的时候记得让v取负数。很多人的代码在v全为正时是对的一旦出现负数某些依赖“非负”的隐性假设就崩了。随机区间加负值是检验差分代码健壮性的标准动作。4. 进阶套路树上差分与差分约束系统4.1 树上点差分与边差分树上的路径修改本质上也是一次“区间修改”只不过区间从数组上的一段变成了树上的一条路径。差分思想在这里的表现形式是两个端点各加一次、LCA 处减掉、LCA 的父节点再减掉。点差分对路径上的每个点加vdiff[u] v diff[v] v diff[lca] - v diff[parent(lca)] - v统计时从叶子往根做子树求和每个点的最终值就是它自己的diff加上所有子节点的和。边差分对路径上的每条边加vdiff[u] v diff[v] v diff[lca] - 2 * v统计时同样自底向上求和但每个点的求和结果代表的是“这个点到它父节点这条边”的值根节点没有意义需要丢弃。两者的差异点很值得琢磨。点差分多减了一个parent(lca)是因为路径上的点是包含 LCA 的子树求和时 LCA 本身会被算进去需要单独调整父节点。边差分里路径不包含 LCA 上方的边减两次就正好抵消干净。这个区别如果不理解写出来就会“点上多算一个根、边上少算一条边”而且在小数据上可能碰巧对。树上差分的前提是求出 LCA。常用的做法是倍增、树链剖分或者 Tarjan 离线。倍增最好写代码短、常数小O(log n)一次查询Tarjan 离线在单次查询量大时更快但要先把所有查询存起来属于离线算法。这一块的代码较长不建议在比赛里默写提前准备好模板更稳。4.2 差分约束把不等式变成最短路差分约束是另一类“差分”问题名字里有差分但它处理的是变量之间的差值不等式和一维差分数组不是同一样东西。不过思想上有共通之处都在考虑“相对变化”。差分约束的标准形式是给一堆形如x_i - x_j c的不等式问是否存在一组解、或者求某个变量的最大/最小值。解法是建图对每条x_i - x_j c从j向i连一条权为c的有向边。满足所有不等式的一组解对应的是这个图上从超级源点出发的最短路。之所以是最短路因为dis[i] dis[j] c恰好就是松弛条件全部满足意味着所有不等式同时成立。如果图里存在负环说明约束无解——转一圈回来要求x x矛盾。所以判负环是差分约束的第一件事通常用 SPFA 或者 Bellman-Ford因为边权可以是负数。有几点实操经验建超级源点向每个点连一条权为 0 的边保证图连通否则有的点根本走不到判不出它的负环。如果题目要求的是x_i - x_j c等价于x_j - x_i -c边的方向要反过来。如果要求最大值跑最短路要求最小值跑最长路把不等号方向统一之后处理。整数解的问题要注意最短路的解是整数因为边权是整数这一点可以直接用。对于全部变量加一个常数仍然满足约束的性质可以让某个变量的值固定为 0作为基准。差分约束的题目有种“看不出是图论”的迷惑感识别信号是题目给了一堆差值关系问是否可行、或者问某个量的极值。看到这种描述先往不等式建图的方向想多半没错。4.3 差分与二分、离散化的组合实际题目里差分很少单独出现它更像是一个组件被嵌在别的框架里。差分 二分是常见组合。典型题型是“求最小的最大负载”或“最少需要多少次操作”。做法是二分答案然后用差分在O(n)时间内检查该答案是否可行。比如有一类调度问题给定若干个资源请求区间问至少需要多少资源才能全部满足答案是最大重叠数——这个最大重叠数就能用差分一次统计出来。再比如“是否能通过若干次区间操作把数组变成目标数组”也常通过二分操作次数 差分检查。差分 离散化解决坐标跨度大的问题。做法是把所有会用到的坐标端点收集起来排序去重然后用原坐标在排序后的位置做差分。这里有个陷阱如果题目关心的是“覆盖了多少个整数点”离散化之后两个相邻离散点之间的空隙也要当成一个长度来算不能简单地当成相邻。处理方式是把区间表示成左闭右开的[l, r1)或者额外维护离散点之间的实际距离。差分 扫描线是矩形面积并那一类题的标配。扫描线沿一个方向推进每遇到矩形的两条竖边就在差分数组配合线段树上做加减实时维护被覆盖的总长度。这里的“差分”不是简单的数组累加而是叠加在线段树的懒标记上本质上还是同一个思路只在变化的边界处动手。二维差分 前缀和则常用于图像处理类的模拟题比如批量给若干矩形区域叠加亮度、最后统计某个阈值以上的像素个数。有一次我做一个模拟的图像采样 demo需要在上万次矩形涂抹后统计结果用二维差分把单次涂抹从O(面积)降到O(1)整体跑下来从几秒降到几十毫秒效果非常直观。5. 常见问题与排查技巧实录5.1 高频错误速查表差分代码的错误模式其实高度集中我把自己和身边人踩过的整理成一张表遇到问题时先对着表扫一遍命中率很高。现象最可能的原因排查动作结果整体偏移一个常数初始数组没有先构造差分直接在空差分上做修改打印d的初值确认是否包含原数组数组尾部一片错值r1越界写坏内存检查数组长度是否为n2区间右端点总是差 1更新写成了d[r] - v对照公式确认是r1二维结果右下角区域多算漏了d[x21][y21] v检查四行是否齐全符号是否 - - 二维结果左下、右上区域异常减号位置写反用 2x2 小数据手工推演一遍树上路径结果在 LCA 处多 1点差分漏了parent(lca)的减补上diff[parent(lca)] - v树边差分根节点值非 0统计时没有丢弃根输出时跳过根负数测试就崩某处用了“非负”假设比如取模后比较全局搜一遍取模和最小值处理这张表里最想强调的是第一行。很多人以为差分数组的初值“默认都是 0”忘了原数组可能不是全零结果所有修改都在错误的基础上叠加。一个保险的写法是永远把原数组当作一组单点区间修改统一走range_add这样只有一条代码路径不会出现“构造”和“修改”两套逻辑对不上的情况。5.2 我的调试流程写了这么多年我形成了一个固定的差分调试流程四步走基本能在五分钟内定位问题。第一步先写暴力。不管题目多简单先把暴力版本写出来能跑通、能输出结果。这一步花的时间通常不超过三分钟但它给了你一个可对拍的基准。差分这类“改写结构”的优化没有基准就是在盲飞。第二步用小数据对拍。随机生成规模 5 到 8 的输入跑个几百组断言两个版本结果一致。小数据的好处是错误一定会暴露而且暴露的位置你能手工推演。大数据的错误往往只有一两个格子不对很难定位。第三步打印中间态。如果对拍挂了把最后一组出错的输入单独拿出来跑打印差分数组在每次修改后的状态、打印还原过程中的前缀和。差分的问题八成出在“某次修改加错了位置”把每次修改后的d打出来一眼就能看出哪次不对。第四步手工推演。挑一组最小的数据比如长度 3、一次修改拿笔画一遍差分数组怎么变、前缀和怎么还原和程序的输出逐位对照。这一步看着笨但它是唯一能让你真正理解“为什么错”的方法。调完一次手工推演之后同类问题基本不会再犯。注意不要在没有暴力版本的情况下直接调试差分代码。差分的结果是“最终态”中间态被压缩掉了直接看结果很难判断是哪一步出的问题。5.3 几处容易忽略的实战细节除了常规错误还有一些细节是文档里不会写、只有实际写过才会注意到的。差分数组的值域可能超出预期。每次区间修改都会在差分数组上留下v和-v如果m次修改都落在同一个位置附近该位置的差分值可能达到m * v。用 32 位整数时m和v都在 10 的 5 次方量级乘积就是 10 的 10 次方直接溢出。养成习惯涉及累加的数组一律用 64 位整数。这个坑我在一道统计类题目上踩过结果在本地小数据全对交上去一半用例错查了半小时才发现是溢出。下标从 0 开始和从 1 开始不要混用。差分的公式在两种下标体系下都能成立但表达形式略有差异。比如 0 下标体系下d[0] a[0]更新[l, r]是d[l] v; d[r1] - v但r1可能等于n需要保证数组长度是n1。如果代码里一半用 0 下标、一半用 1 下标边界判断会非常容易错。我的建议是只要用了差分全局统一切到 1 下标原始数据读入时直接放到a[1..n]后面所有逻辑都在 1 下标体系里写心智能负担最小。多次还原要注意状态清理。如果在一个循环里反复做差分和还原比如二分答案的每一轮检查每次都要把差分数组重置为全零。复用一个全局数组时忘记清零是最常见的“莫名其妙错误”。写法上用局部变量重新分配更安全虽然有一点分配开销但避免了状态污染。前缀和还原时的累加顺序。一维还原必须从左到右二维还原必须从左上到右下。如果顺序反了累加依赖的前驱值还没算出来结果就是错的。这个错误在二维里特别隐蔽因为有时候顺序反了也能跑出“看起来合理”的结果。查询次数少时暴力可能更快。差分的优势在于修改次数多、查询次数少。如果只有两次区间修改直接暴力循环改就好了没必要引入差分。判断标准是m修改次数和n区间平均长度的乘积如果m * n在可接受范围内暴力代码更短、更不容易错。工程上可读性和正确性永远优先于理论复杂度。差分的“逆”不是只有前缀和。前面一直说差分和前缀和互为逆运算但在某些变体里“还原”可能是别的操作。比如在树上还原是做子树求和在扫描线里还原是通过线段树维护区间覆盖计数。这些场景下公式形态变了但“只在变化处记录增量、最后统一传播”的内核没变。抓住这个内核遇到变体才不会慌。提示判断一道题该不该用差分问自己三个问题——是不是批量区间修改是不是最后才查询运算符有没有逆元三个都是“是”差分基本就是最优解有一个是“否”就得换工具了。最后分享一个我自己的习惯每次写完差分代码不管多自信都会在最后加一行输出把还原后的数组完整打印出来用眼睛扫一眼首尾和中间几个位置。这一眼花不了两秒钟但拦下过好几次“数组没开够”和“忘记清空”的问题。差分这类结构简单但边界琐碎的技巧靠的不是聪明是流程。 
长河君 · 2026/10/31 12:54:19 · 阅读 1.2k 从一维差分到树上差分：区间修改与差分约束实战
差分这个东西我第一次接触时是在一道区间加、单点查询的题上当时用线段树硬写写了八十多行还调了半天标记下推。后来有位做题很猛的朋友看了一眼说这题差分十行就完了。那一刻的感受挺复杂——不是不会是没想到还能这么想。差分原理本身不复杂难的是在什么场景下能想到用它以及边界到底该怎么算。这篇就把差分从小到大拆一遍从一维差分数组的构造与还原到二维差分矩形的四次加减再到树上差分和差分约束这类进阶玩法最后把我这些年踩过的坑摆出来。适合刚学完前缀和、想找一个更省事的区间操作思路的同学也适合写了几年代码但对“差分”只停留在背模板层面的朋友。1. 差分到底是什么从一道刷墙题说起1.1 走廊刷墙差分最朴素的样子假设有一条很长的走廊墙上贴着 1000 块瓷砖编号 1 到 1000。现在有三批工人来刷漆第一批刷第 100 到第 300 块第二批刷第 250 到第 600 块第三批刷第 500 到第 900 块。问最后每块瓷砖被刷了几次。最直接的做法是每来一批工人就从起点到终点挨个加一。三批工人加起来总操作量大概是 200 350 400 950 次。这个量级还能接受但如果瓷砖有一百万块、工人有十万批呢每次操作平均覆盖一半区间总量就是五千万次虽然勉强能跑但已经很不舒服了。换个思路想我不记录每块砖被刷了几次我只记录**“从哪一块开始多了从哪一块开始少了”**。第一批工人来我在第 100 块的位置记一个“1”在第 301 块的位置记一个“-1”。意思是从 100 开始刷漆次数比前面多 1从 301 开始又回到原来的水平。三批工人都这么记最后我只需要从第 1 块走到第 1000 块一路累加这些“变化量”就能还原出每块砖的实际次数。三批工人只产生 6 次记录操作。这就是差分的全部精髓把一次区间修改压缩成两次单点修改。这个“走廊刷墙”的模型看着像小孩过家家但它对应的实际场景非常多某段时间内的并发请求计数、某个温度区间内的采样点累加、某段里程内的费用叠加、游戏里某个坐标范围内的伤害区域判定。凡是“区间统一加一个值最后一次性统计”的需求差分都是第一顺位要考虑的工具。1.2 差分与前缀和是一对逆运算很多人学差分时会觉得它和前缀和有点像确实如此而且这个关系值得说透因为它是后面所有推导的地基。前缀和做的事是给一个数组a构造一个数组s满足s[i] a[1] a[2] ... a[i]。也就是把“累加”这个动作提前算好之后任意区间和都能用s[r] - s[l-1]一次减法拿到。差分做的事正好反过来给一个数组a构造一个数组d满足d[i] a[i] - a[i-1]约定a[0] 0。也就是把“相邻差”显式存下来。两者的关系可以用一句话概括对差分数组求前缀和就还原出原数组对原数组求差分就得到差分数组。这两个操作互为逆运算就像加密和解密。这个逆运算关系解释了一个很关键的疑问为什么区间更新时是d[l] v和d[r1] - v因为还原的时候要做前缀和d[l]加上v之后从l开始往后的所有位置在累加时都会多算一个v为了让它只影响到r为止必须在r1处把这个v抵消掉也就是减去v。理解了这个“抵消”的动机就不需要死记公式了。顺便说一句这个思路可以一直往上叠前缀和的前缀和、差分再差分。二维前缀和的逆运算就是二维差分树上路径和的逆运算就是树上差分。套路是同一个套路只是维度变了。1.3 同名不同物几个容易混淆的“差分”这里得插一段辨析因为“差分”这个词在不同领域指的东西差别很大搜资料的时候很容易撞车。领域“差分”指什么核心用途算法/数据结构相邻元素的差构成的数组把区间修改降为单点修改信号与电子两根线上传输幅度相反、相位互补的信号抵消共模干扰提升传输质量数值计算用差分近似导数如f(x) ≈ (f(xh)-f(x))/h解微分方程、数值仿真优化算法差分演化算法用个体间差分向量做变异连续空间的全局搜索定位技术差分定位用基准站修正流动站误差提高定位精度它们共同的哲学其实是同一个不直接处理绝对值而处理“相对变化”。绝对值携带的信息多但也更“重”变化量更轻、更容易被压缩和传递。这个视角在你做任何性能优化的时候都用得上——系统里真正需要传的往往不是全量数据而是增量。不过往下走重心还是放在算法层面的一维差分、二维差分和树上差分上其他几个只是帮你建立“差分是一种通用思维”的直觉不至于看到标题就只想到一个数组。2. 一维差分数组的构造、更新与还原2.1 构造一次遍历就能搞定一维差分数组的构造非常轻一趟循环就完事。用 Python 写出来大概是这样def build_diff(a): n len(a) d [0] * (n 2) # 多开两位给 r1 留空间 for i in range(1, n 1): d[i] a[i] - a[i - 1] # a[0] 约定为 0 return d这段代码里有几个细节值得掰开说。第一下标从 1 开始。这是竞赛和工程里都很常见的约定好处是a[i-1]不会越界d[r1]也天然合法。代价是数组要开n2大小不能用 0 下标直接对应原始数据。如果你更喜欢 0 下标也能写公式变成d[i] a[i] - a[i-1]i0、d[0] a[0]更新时变成d[l] v、d[r1] - v只是r1有可能等于n需要在数组尾部补一位。两种写法都对但一个项目里最好统一一种混着用是低级 bug 的温床。第二d的初值不需要真的从a构造。如果题目的初始数组全为 0只做区间加操作那么d直接全零初始化即可最后统一前缀和还原。只有当原始数组非零、并且需要在它基础上继续做区间修改时才需要先构造差分。这一点很多人会绕进去明明可以直接在差分数组上累加a的影响却非要把a整体构造一遍白白多写一段代码。换一种更省事的等价写法把“给a[i]赋初值”也看成一次“区间[i, i]加上a[i]”的操作那么所有初始化都统一成区间加代码路径就只有一个不容易漏。2.2 区间更新为什么只动两个位置区间[l, r]整体加v核心就两行def range_add(d, l, r, v): d[l] v d[r 1] - v为什么是这两行前面用“抵消”解释过了这里再从另一个角度看一遍差分数组的每一项d[i]表示“第i个位置相对于第i-1个位置的变化量”。给[l, r]全体加v等于在l处凭空多出一个台阶相对前一位增加了v在r1处这个台阶得落回去相对前一位减少了v。区间内部的相邻关系没有变所以内部的差分值一个都不用动。这个“只有台阶的两端会变”的直觉很重要它直接推广到了二维二维差分修改一个矩形只影响矩形的四个角点因为矩形内部相邻的差分关系同样不变。还原过程就是一次前缀和def restore(d, n): a [0] * (n 2) cur 0 for i in range(1, n 1): cur d[i] a[i] cur return a注意这里的cur是滚动累加的不需要额外开一个前缀和数组。如果只需要最终结果、不需要保留中间态这个写法能省一半内存。复杂度账本很清楚构造O(n)每次区间修改O(1)最后一次还原O(n)。总共m次修改的话总复杂度O(n m)。对比暴力的O(n*m)当n和m都在十万量级时差距是十个数量级——这不是优化这是换了一个问题。2.3 边界与数组开多大才不越界差分代码写挂十次里有七次是数组开小了。d[r1] - v里的r1有可能等于n1如果d只开了n长度这里直接越界。Python 里会抛异常C 里是未定义行为可能不报错但结果莫名其妙。稳妥的写法是统一开n2多出来的两位一位给r1用一位给可能的哨兵用。如果你的更新范围是从 0 开始的下标还要再多考虑一位。宁可多开两个int也不要为了省内存留隐患。另一个容易忽视的边界是空区间。如果l r这两行代码会做出很奇怪的事d[l] v在r1之后等于在一个不存在的位置加了个值前缀和还原时这个值会一直影响到数组末尾结果全错。正常逻辑下不该出现l r但如果区间是算出来的比如两个坐标取交一定要在更新前加一句判断。还有一种是区间端点超出数据范围。比如坐标压缩之后算出来的r1大于实际元素个数这时候减操作落在了一个永远不会被访问的位置看起来“没生效”实际是生效了但你没还原到那里。这类问题的排查方式是输出整个差分数组看看有没有哪一位的绝对值大得离谱。提示写完差分代码第一件事是打印整个d数组。差分数组的绝对值通常都很小就是相邻差如果出现一个很大的数说明某次更新加错了位置或者漏了抵消。2.4 适用条件什么时候差分不管用差分不是万能的它有明确的适用边界越界使用会很难受。第一条只适合离线场景。差分的前提是“先把所有修改攒着最后一次性还原”。如果题目要求每次修改之后立刻查询当前状态差分就无能为力了因为还原一次就是O(n)m次查询就退化成O(n*m)。这种在线查询的场景要用线段树、树状数组或者分块。第二条只适合可减的运算。差分依赖“加进去再减出来”这个抵消机制本质上是加法群的逆元。如果运算是取最大值、取最小值、按位与这类没有逆元的操作差分就不成立。这个限制在二维和树上同样存在。第三条修改的值必须与位置无关。区间加一个常数v差分很自然。但如果区间加的是“下标乘v”或者“下标平方乘v”那就不是一阶差分能解决的了需要用到二阶差分或者把式子拆成几项分别维护。这类题在进阶训练里不少见思路是把待维护的量拆成“常数项 下标项 下标平方项”每一项单独开一个差分数组。第四条离散性问题。差分天然处理的是连续整数下标。如果数据是稀疏的、坐标跨度极大比如坐标值到 10 的 9 次方直接开数组会爆内存必须先离散化。离散化之后再差分要注意“区间”在离散化后是否还连续——如果两个相邻离散点之间有大段空隙直接把它们当作相邻来处理可能改变语义。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]是因为左上角的块被加了两次要容斥掉一次。差分数组d定义为s的逆运算把上式移项就得到d[i][j] a[i][j] - a[i-1][j] - a[i][j-1] a[i-1][j-1]这就是二维差分的构造式。它的含义是d[i][j]表示(i,j)这个位置相对于它左边、上边、左上三个邻居的“综合变化量”。还原的时候反过来把a换成用d表达a[i][j] d[i][j] a[i-1][j] a[i][j-1] - a[i-1][j-1]看这个式子和前缀和的递推式长得一模一样这就是“逆运算”的具体体现。写代码的时候还原函数和前缀和函数几乎是同一份代码只是入参不同。3.2 四个角的符号规律与代码给矩形(x1,y1)到(x2,y2)整体加v四行代码def rect_add(d, x1, y1, x2, y2, v): d[x1][y1] v d[x2 1][y1] - v d[x1][y2 1] - v d[x2 1][y2 1] v四个角的符号是 - - 。这个规律怎么记我用的是一个“投影”的思路(x1,y1)是矩形的起点从这里开始“生效”所以是v。(x21,y1)是矩形的下边界外侧从这一行开始“下面不该再受这个v影响”所以-v。(x1,y21)同理是右边界外侧-v。(x21,y21)是右下角外侧这个位置在还原时被前两个减号“减了两次”多减了所以要补回来一次v。这个解释和二维前缀和里的容斥是完全对称的前缀和是“加了两次要减一次”差分是“减了两次要加一次”。记住其中一个另一个自然就出来了。完整的验证代码可以这样写def solve(n, m, ops): d [[0] * (m 2) for _ in range(n 2)] for x1, y1, x2, y2, v in ops: d[x1][y1] v d[x2 1][y1] - v d[x1][y2 1] - v d[x2 1][y2 1] v for i in range(1, n 1): for j in range(1, m 1): d[i][j] d[i - 1][j] d[i][j - 1] - d[i - 1][j - 1] return d原地还原直接把d变成结果矩阵省一个数组。这个写法有个前提d[i][j]在累加之前保存的是差分值累加之后变成真实值两者共用一块内存。只要还原的方向是从左上到右下就不会出现“还没用完就被覆盖”的问题因为d[i][j]只会被它左边、上边、左上用过一次。3.3 小数据暴力对拍验证二维差分的边界比一维更容易出错x21和y21都可能等于n1或m1数组必须开(n2) × (m2)。我一般会在写完差分解法之后立刻写一个暴力版本对拍不超过二十行import random def brute(n, m, ops): a [[0] * (m 1) for _ in range(n 1)] for x1, y1, x2, y2, v in ops: for i in range(x1, x2 1): for j in range(y1, y2 1): a[i][j] v return a for _ in range(500): n, m random.randint(1, 6), random.randint(1, 6) ops [] for _ in range(random.randint(1, 5)): x1 random.randint(1, n) x2 random.randint(x1, n) y1 random.randint(1, m) y2 random.randint(y1, m) ops.append((x1, y1, x2, y2, random.randint(-5, 5))) fast solve(n, m, ops) slow brute(n, m, ops) for i in range(1, n 1): for j in range(1, m 1): assert fast[i][j] slow[i][j], (n, m, ops, i, j)这套对拍我几乎每写一次二维差分都会跑一遍因为二维差分的错误往往不会在大数据上暴露只在小数据的某个边角上错一格。对拍规模控制在 6 以内五百组随机用例跑起来不到一秒性价比极高。另外提一句对拍的时候记得让v取负数。很多人的代码在v全为正时是对的一旦出现负数某些依赖“非负”的隐性假设就崩了。随机区间加负值是检验差分代码健壮性的标准动作。4. 进阶套路树上差分与差分约束系统4.1 树上点差分与边差分树上的路径修改本质上也是一次“区间修改”只不过区间从数组上的一段变成了树上的一条路径。差分思想在这里的表现形式是两个端点各加一次、LCA 处减掉、LCA 的父节点再减掉。点差分对路径上的每个点加vdiff[u] v diff[v] v diff[lca] - v diff[parent(lca)] - v统计时从叶子往根做子树求和每个点的最终值就是它自己的diff加上所有子节点的和。边差分对路径上的每条边加vdiff[u] v diff[v] v diff[lca] - 2 * v统计时同样自底向上求和但每个点的求和结果代表的是“这个点到它父节点这条边”的值根节点没有意义需要丢弃。两者的差异点很值得琢磨。点差分多减了一个parent(lca)是因为路径上的点是包含 LCA 的子树求和时 LCA 本身会被算进去需要单独调整父节点。边差分里路径不包含 LCA 上方的边减两次就正好抵消干净。这个区别如果不理解写出来就会“点上多算一个根、边上少算一条边”而且在小数据上可能碰巧对。树上差分的前提是求出 LCA。常用的做法是倍增、树链剖分或者 Tarjan 离线。倍增最好写代码短、常数小O(log n)一次查询Tarjan 离线在单次查询量大时更快但要先把所有查询存起来属于离线算法。这一块的代码较长不建议在比赛里默写提前准备好模板更稳。4.2 差分约束把不等式变成最短路差分约束是另一类“差分”问题名字里有差分但它处理的是变量之间的差值不等式和一维差分数组不是同一样东西。不过思想上有共通之处都在考虑“相对变化”。差分约束的标准形式是给一堆形如x_i - x_j c的不等式问是否存在一组解、或者求某个变量的最大/最小值。解法是建图对每条x_i - x_j c从j向i连一条权为c的有向边。满足所有不等式的一组解对应的是这个图上从超级源点出发的最短路。之所以是最短路因为dis[i] dis[j] c恰好就是松弛条件全部满足意味着所有不等式同时成立。如果图里存在负环说明约束无解——转一圈回来要求x x矛盾。所以判负环是差分约束的第一件事通常用 SPFA 或者 Bellman-Ford因为边权可以是负数。有几点实操经验建超级源点向每个点连一条权为 0 的边保证图连通否则有的点根本走不到判不出它的负环。如果题目要求的是x_i - x_j c等价于x_j - x_i -c边的方向要反过来。如果要求最大值跑最短路要求最小值跑最长路把不等号方向统一之后处理。整数解的问题要注意最短路的解是整数因为边权是整数这一点可以直接用。对于全部变量加一个常数仍然满足约束的性质可以让某个变量的值固定为 0作为基准。差分约束的题目有种“看不出是图论”的迷惑感识别信号是题目给了一堆差值关系问是否可行、或者问某个量的极值。看到这种描述先往不等式建图的方向想多半没错。4.3 差分与二分、离散化的组合实际题目里差分很少单独出现它更像是一个组件被嵌在别的框架里。差分 二分是常见组合。典型题型是“求最小的最大负载”或“最少需要多少次操作”。做法是二分答案然后用差分在O(n)时间内检查该答案是否可行。比如有一类调度问题给定若干个资源请求区间问至少需要多少资源才能全部满足答案是最大重叠数——这个最大重叠数就能用差分一次统计出来。再比如“是否能通过若干次区间操作把数组变成目标数组”也常通过二分操作次数 差分检查。差分 离散化解决坐标跨度大的问题。做法是把所有会用到的坐标端点收集起来排序去重然后用原坐标在排序后的位置做差分。这里有个陷阱如果题目关心的是“覆盖了多少个整数点”离散化之后两个相邻离散点之间的空隙也要当成一个长度来算不能简单地当成相邻。处理方式是把区间表示成左闭右开的[l, r1)或者额外维护离散点之间的实际距离。差分 扫描线是矩形面积并那一类题的标配。扫描线沿一个方向推进每遇到矩形的两条竖边就在差分数组配合线段树上做加减实时维护被覆盖的总长度。这里的“差分”不是简单的数组累加而是叠加在线段树的懒标记上本质上还是同一个思路只在变化的边界处动手。二维差分 前缀和则常用于图像处理类的模拟题比如批量给若干矩形区域叠加亮度、最后统计某个阈值以上的像素个数。有一次我做一个模拟的图像采样 demo需要在上万次矩形涂抹后统计结果用二维差分把单次涂抹从O(面积)降到O(1)整体跑下来从几秒降到几十毫秒效果非常直观。5. 常见问题与排查技巧实录5.1 高频错误速查表差分代码的错误模式其实高度集中我把自己和身边人踩过的整理成一张表遇到问题时先对着表扫一遍命中率很高。现象最可能的原因排查动作结果整体偏移一个常数初始数组没有先构造差分直接在空差分上做修改打印d的初值确认是否包含原数组数组尾部一片错值r1越界写坏内存检查数组长度是否为n2区间右端点总是差 1更新写成了d[r] - v对照公式确认是r1二维结果右下角区域多算漏了d[x21][y21] v检查四行是否齐全符号是否 - - 二维结果左下、右上区域异常减号位置写反用 2x2 小数据手工推演一遍树上路径结果在 LCA 处多 1点差分漏了parent(lca)的减补上diff[parent(lca)] - v树边差分根节点值非 0统计时没有丢弃根输出时跳过根负数测试就崩某处用了“非负”假设比如取模后比较全局搜一遍取模和最小值处理这张表里最想强调的是第一行。很多人以为差分数组的初值“默认都是 0”忘了原数组可能不是全零结果所有修改都在错误的基础上叠加。一个保险的写法是永远把原数组当作一组单点区间修改统一走range_add这样只有一条代码路径不会出现“构造”和“修改”两套逻辑对不上的情况。5.2 我的调试流程写了这么多年我形成了一个固定的差分调试流程四步走基本能在五分钟内定位问题。第一步先写暴力。不管题目多简单先把暴力版本写出来能跑通、能输出结果。这一步花的时间通常不超过三分钟但它给了你一个可对拍的基准。差分这类“改写结构”的优化没有基准就是在盲飞。第二步用小数据对拍。随机生成规模 5 到 8 的输入跑个几百组断言两个版本结果一致。小数据的好处是错误一定会暴露而且暴露的位置你能手工推演。大数据的错误往往只有一两个格子不对很难定位。第三步打印中间态。如果对拍挂了把最后一组出错的输入单独拿出来跑打印差分数组在每次修改后的状态、打印还原过程中的前缀和。差分的问题八成出在“某次修改加错了位置”把每次修改后的d打出来一眼就能看出哪次不对。第四步手工推演。挑一组最小的数据比如长度 3、一次修改拿笔画一遍差分数组怎么变、前缀和怎么还原和程序的输出逐位对照。这一步看着笨但它是唯一能让你真正理解“为什么错”的方法。调完一次手工推演之后同类问题基本不会再犯。注意不要在没有暴力版本的情况下直接调试差分代码。差分的结果是“最终态”中间态被压缩掉了直接看结果很难判断是哪一步出的问题。5.3 几处容易忽略的实战细节除了常规错误还有一些细节是文档里不会写、只有实际写过才会注意到的。差分数组的值域可能超出预期。每次区间修改都会在差分数组上留下v和-v如果m次修改都落在同一个位置附近该位置的差分值可能达到m * v。用 32 位整数时m和v都在 10 的 5 次方量级乘积就是 10 的 10 次方直接溢出。养成习惯涉及累加的数组一律用 64 位整数。这个坑我在一道统计类题目上踩过结果在本地小数据全对交上去一半用例错查了半小时才发现是溢出。下标从 0 开始和从 1 开始不要混用。差分的公式在两种下标体系下都能成立但表达形式略有差异。比如 0 下标体系下d[0] a[0]更新[l, r]是d[l] v; d[r1] - v但r1可能等于n需要保证数组长度是n1。如果代码里一半用 0 下标、一半用 1 下标边界判断会非常容易错。我的建议是只要用了差分全局统一切到 1 下标原始数据读入时直接放到a[1..n]后面所有逻辑都在 1 下标体系里写心智能负担最小。多次还原要注意状态清理。如果在一个循环里反复做差分和还原比如二分答案的每一轮检查每次都要把差分数组重置为全零。复用一个全局数组时忘记清零是最常见的“莫名其妙错误”。写法上用局部变量重新分配更安全虽然有一点分配开销但避免了状态污染。前缀和还原时的累加顺序。一维还原必须从左到右二维还原必须从左上到右下。如果顺序反了累加依赖的前驱值还没算出来结果就是错的。这个错误在二维里特别隐蔽因为有时候顺序反了也能跑出“看起来合理”的结果。查询次数少时暴力可能更快。差分的优势在于修改次数多、查询次数少。如果只有两次区间修改直接暴力循环改就好了没必要引入差分。判断标准是m修改次数和n区间平均长度的乘积如果m * n在可接受范围内暴力代码更短、更不容易错。工程上可读性和正确性永远优先于理论复杂度。差分的“逆”不是只有前缀和。前面一直说差分和前缀和互为逆运算但在某些变体里“还原”可能是别的操作。比如在树上还原是做子树求和在扫描线里还原是通过线段树维护区间覆盖计数。这些场景下公式形态变了但“只在变化处记录增量、最后统一传播”的内核没变。抓住这个内核遇到变体才不会慌。提示判断一道题该不该用差分问自己三个问题——是不是批量区间修改是不是最后才查询运算符有没有逆元三个都是“是”差分基本就是最优解有一个是“否”就得换工具了。最后分享一个我自己的习惯每次写完差分代码不管多自信都会在最后加一行输出把还原后的数组完整打印出来用眼睛扫一眼首尾和中间几个位置。这一眼花不了两秒钟但拦下过好几次“数组没开够”和“忘记清空”的问题。差分这类结构简单但边界琐碎的技巧靠的不是聪明是流程。