企业官网建设流程全解析

差分这个东西，我第一次接触时是在一道区间加、单点查询的题上，当时用线段树硬写，写了八十多行，还调了半天标记下推。后来有位做题很猛的朋友看了一眼说，这题差分十行就完了。那一刻的感受挺复杂——不是不会，是没想到还能这么想。差分原理本身不复杂，难的是在什么场景下能想到用它，以及边界到底该怎么算。这篇就把差分从小到大拆一遍：从一维差分数组的构造与还原，到二维差分矩形的四次加减，再到树上差分和差分约束这类进阶玩法，最后把我这些年踩过的坑摆出来。适合刚学完前缀和、想找一个更省事的区间操作思路的同学，也适合写了几年代码但对“差分”只停留在背模板层面的朋友。

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[r+1] -= v？因为还原的时候要做前缀和，d[l]加上v之后，从l开始往后的所有位置在累加时都会多算一个v；为了让它只影响到r为止，必须在r+1处把这个v抵消掉，也就是减去v。理解了这个“抵消”的动机，就不需要死记公式了。

顺便说一句，这个思路可以一直往上叠：前缀和的前缀和、差分再差分。二维前缀和的逆运算就是二维差分，树上路径和的逆运算就是树上差分。套路是同一个套路，只是维度变了。

1.3 同名不同物：几个容易混淆的“差分”

这里得插一段辨析，因为“差分”这个词在不同领域指的东西差别很大，搜资料的时候很容易撞车。

它们共同的哲学其实是同一个：不直接处理绝对值，而处理“相对变化”。绝对值携带的信息多但也更“重”，变化量更轻、更容易被压缩和传递。这个视角在你做任何性能优化的时候都用得上——系统里真正需要传的往往不是全量数据，而是增量。

不过往下走，重心还是放在算法层面的一维差分、二维差分和树上差分上，其他几个只是帮你建立“差分是一种通用思维”的直觉，不至于看到标题就只想到一个数组。

2. 一维差分数组的构造、更新与还原

2.1 构造：一次遍历就能搞定

一维差分数组的构造非常轻，一趟循环就完事。用 Python 写出来大概是这样：

def build_diff(a): n = len(a) d = [0] * (n + 2) # 多开两位，给 r+1 留空间 for i in range(1, n + 1): d[i] = a[i] - a[i - 1] # a[0] 约定为 0 return d

这段代码里有几个细节值得掰开说。

第一，下标从 1 开始。这是竞赛和工程里都很常见的约定，好处是a[i-1]不会越界，d[r+1]也天然合法。代价是数组要开n+2大小，不能用 0 下标直接对应原始数据。如果你更喜欢 0 下标，也能写，公式变成d[i] = a[i] - a[i-1]（i>0）、d[0] = a[0]，更新时变成d[l] += v、d[r+1] -= v，只是r+1有可能等于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），在r+1处这个台阶得落回去（相对前一位减少了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[r+1] -= v里的r+1有可能等于n+1，如果d只开了n长度，这里直接越界。Python 里会抛异常，C++ 里是未定义行为，可能不报错但结果莫名其妙。

稳妥的写法是统一开n+2，多出来的两位一位给r+1用，一位给可能的哨兵用。如果你的更新范围是从 0 开始的下标，还要再多考虑一位。宁可多开两个int，也不要为了省内存留隐患。

另一个容易忽视的边界是空区间。如果l > r，这两行代码会做出很奇怪的事：d[l] += v在r+1之后，等于在一个不存在的位置加了个值，前缀和还原时这个值会一直影响到数组末尾，结果全错。正常逻辑下不该出现l > r，但如果区间是算出来的（比如两个坐标取交），一定要在更新前加一句判断。

还有一种是区间端点超出数据范围。比如坐标压缩之后算出来的r+1大于实际元素个数，这时候减操作落在了一个永远不会被访问的位置，看起来“没生效”，实际是生效了但你没还原到那里。这类问题的排查方式是：输出整个差分数组，看看有没有哪一位的绝对值大得离谱。

提示：写完差分代码，第一件事是打印整个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。
• (x2+1,y1)是矩形的下边界外侧，从这一行开始，“下面不该再受这个v影响”，所以-v。
• (x1,y2+1)同理，是右边界外侧，-v。
• (x2+1,y2+1)是右下角外侧，这个位置在还原时被前两个减号“减了两次”，多减了，所以要补回来一次，+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 小数据暴力对拍验证

二维差分的边界比一维更容易出错，x2+1和y2+1都可能等于n+1或m+1，数组必须开(n+2) × (m+2)。我一般会在写完差分解法之后，立刻写一个暴力版本对拍，不超过二十行：

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 的父节点再减掉。

点差分（对路径上的每个点加v）：

diff[u] += v diff[v] += v diff[lca] -= v diff[parent(lca)] -= v

统计时从叶子往根做子树求和，每个点的最终值就是它自己的diff加上所有子节点的和。

边差分（对路径上的每条边加v）：

diff[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, r+1)，或者额外维护离散点之间的实际距离。

差分 + 扫描线是矩形面积并那一类题的标配。扫描线沿一个方向推进，每遇到矩形的两条竖边就在差分数组（配合线段树）上做加减，实时维护被覆盖的总长度。这里的“差分”不是简单的数组累加，而是叠加在线段树的懒标记上，本质上还是同一个思路：只在变化的边界处动手。

二维差分 + 前缀和则常用于图像处理类的模拟题，比如批量给若干矩形区域叠加亮度、最后统计某个阈值以上的像素个数。有一次我做一个模拟的图像采样 demo，需要在上万次矩形涂抹后统计结果，用二维差分把单次涂抹从O(面积)降到O(1)，整体跑下来从几秒降到几十毫秒，效果非常直观。

5. 常见问题与排查技巧实录

5.1 高频错误速查表

差分代码的错误模式其实高度集中，我把自己和身边人踩过的整理成一张表，遇到问题时先对着表扫一遍，命中率很高。

这张表里最想强调的是第一行。很多人以为差分数组的初值“默认都是 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[r+1] -= v，但r+1可能等于n，需要保证数组长度是n+1。如果代码里一半用 0 下标、一半用 1 下标，边界判断会非常容易错。我的建议是：只要用了差分，全局统一切到 1 下标，原始数据读入时直接放到a[1..n]，后面所有逻辑都在 1 下标体系里写，心智能负担最小。

多次还原要注意状态清理。如果在一个循环里反复做差分和还原（比如二分答案的每一轮检查），每次都要把差分数组重置为全零。复用一个全局数组时，忘记清零是最常见的“莫名其妙错误”。写法上用局部变量重新分配更安全，虽然有一点分配开销，但避免了状态污染。

前缀和还原时的累加顺序。一维还原必须从左到右，二维还原必须从左上到右下。如果顺序反了，累加依赖的前驱值还没算出来，结果就是错的。这个错误在二维里特别隐蔽，因为有时候顺序反了也能跑出“看起来合理”的结果。

查询次数少时，暴力可能更快。差分的优势在于修改次数多、查询次数少。如果只有两次区间修改，直接暴力循环改就好了，没必要引入差分。判断标准是m（修改次数）和n（区间平均长度）的乘积，如果m * n在可接受范围内，暴力代码更短、更不容易错。工程上，可读性和正确性永远优先于理论复杂度。

差分的“逆”不是只有前缀和。前面一直说差分和前缀和互为逆运算，但在某些变体里，“还原”可能是别的操作。比如在树上，还原是做子树求和；在扫描线里，还原是通过线段树维护区间覆盖计数。这些场景下，公式形态变了，但“只在变化处记录增量、最后统一传播”的内核没变。抓住这个内核，遇到变体才不会慌。

提示：判断一道题该不该用差分，问自己三个问题——是不是批量区间修改？是不是最后才查询？运算符有没有逆元？三个都是“是”，差分基本就是最优解；有一个是“否”，就得换工具了。

最后分享一个我自己的习惯：每次写完差分代码，不管多自信，都会在最后加一行输出，把还原后的数组完整打印出来，用眼睛扫一眼首尾和中间几个位置。这一眼花不了两秒钟，但拦下过好几次“数组没开够”和“忘记清空”的问题。差分这类结构简单但边界琐碎的技巧，靠的不是聪明，是流程。