如果你刷过算法题或者哪怕只是在业务代码里处理过时间序列、累计统计这类需求应该对下面这个场景不陌生一个长度为 n 的数组内存完全放得下但你要反复做区间操作——要么问 sum(l,r)要么把区间 l..r 同时加一个数。第一时间想到的往往是 for 循环可当 n 和 m 都到 10^5 甚至 10^6 时最坏情况就是 10^10 次运算比赛和面试基本都稳挂。其实这两个高频问题分别对应两个极其基础的工具前缀和和差分。前缀和把区间求和变成两个前缀和的减法差分把区间加法变成两个端点上的标记而且它们互为逆运算——一个是累计一个是差值。这篇文章我就从零开始把这套东西讲透覆盖一维、二维矩阵和树上场景最后把我在实战中踩过的坑一并列出来。1. 前缀和把区间查询从 O(n) 降到 O(1)1.1 前缀和的本质是一本流水账设原数组 a下标从 1 开始。前缀和数组 pre[i] 表示 a[1] 累加到 a[i] 的总和递推式只有一条pre[i] pre[i - 1] a[i]求区间 [l, r] 的和直接用 pre[r] - pre[l - 1]。为什么它能成立我习惯把它理解成一本流水账a 是每天的花销pre[i] 是到第 i 天为止的累计花销。要问第 l 天到第 r 天总共花了多少用前 r 天的累计减去前 l-1 天的累计中间那一截自然就出来了。这里依赖的数学性质其实只有加法结合律和减法还原所以它非常稳定。你可能会想这有什么难的但前缀和真正的价值在于复杂度。预处理一遍 O(n)之后每次区间查询都是 O(1)。如果查询次数是 m暴力做就是 O(nm)前缀和变成 O(n m)。当 n 和 m 都在 10^5 这个量级时差距是千万级别到毫秒级别的差距。我常说生活中的余额就是一个前缀和模型。银行不会为每笔转账单独记住流水段它只记录每个时刻的余额你要某段时间的明细把余额相减再配合筛选就行。一旦你意识到累计量能被减法还原出区间量很多问题的第一步就清晰了。1.2 代码实现里的下标细节先看最标准的实现。C 版本#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorlong long a(n 1, 0), pre(n 1, 0); for (int i 1; i n; i) { cin a[i]; pre[i] pre[i - 1] a[i]; } auto query [](int l, int r) { return pre[r] - pre[l - 1]; }; // 示例查询区间 [2, 4] cout query(2, 4) endl; return 0; }Python 版本也很简单n int(input()) a [0] list(map(int, input().split())) pre [0] * (n 1) for i in range(1, n 1): pre[i] pre[i - 1] a[i] def query(l, r): return pre[r] - pre[l - 1] print(query(2, 4))很多新手最容易栽在下标上。我的建议是只要写前缀和一律让数组下标从 1 开始把下标 0 空出来。这样 query(l, r) 里的 pre[l - 1] 永远不会访问到负下标代码逻辑也不用为 l 1 单独写分支。如果你非要坚持 0-indexed那要注意你的查询区间很可能变成左闭右开 [l, r)也就是 pre[r] - pre[l]两个模型千万别混用。1.3 前缀思想不只是求和前缀和最常见的进阶玩法是前缀异或。把加法换成异或得到 preXor[i] preXor[i - 1] ^ a[i]区间异或结果就是 preXor[r] ^ preXor[l - 1]。原理是异或两次同一个数会抵消和加法减法是同一个逻辑。前缀积也能做但在取模场景下要配合逆元区间积等于 preMul[r] 乘上 preMul[l - 1] 的逆元。如果只是普通整数直接相除就行不过要注意除零和溢出问题。还有一个非常高频的面试题变形统计和等于 k 的连续子数组个数。暴力是 O(n^2)但用前缀和配合哈希表可以做到 O(n)。核心思路是遍历到位置 j 时前缀和为 pre[j]如果之前某个位置 i 的前缀和 pre[i] 等于 pre[j] - k那么 (i1) 到 j 这一段的和就是 k。于是问题变成了统计 pre[i] 出现的次数一个哈希表就搞定了。不过需要提醒一个边界前缀最大值、前缀最小值这种是不能用两个前缀做差来还原任意区间最值的因为最值运算不可逆。遇到区间最值题目别硬套前缀和老老实实走线段树或者 ST 表。2. 差分把区间修改从 O(n) 降到 O(1)2.1 差分数组到底存了什么如果说前缀和记录的是累计状态那差分数组记录的就是变化量。定义很简单diff[i] a[i] - a[i - 1]其中约定 a[0] 0所以 diff[1] a[1]。你会发现一个有趣的事实对 diff 数组求前缀和恰好能还原出原数组 a。也就是说a 是 diff 的前缀和数组。这两个概念就像照镜子一样前缀和是正着看差分是反着看。用个具体例子。a [2, 5, 9, 1, 4]那么diff[1] 2 diff[2] 5 - 2 3 diff[3] 9 - 5 4 diff[4] 1 - 9 -8 diff[5] 4 - 1 3对 diff 累加2 3 4 - 8 3 4正好是 a[5]。这就是差分和前缀和互逆的最直观体现。2.2 区间加一次操作就这么点东西现在问题是给区间 [l, r] 整体加 v差分数组要怎么改答案是两句diff[l] v diff[r 1] - v为什么两个端点就够了因为差分描述的是相邻元素的差值。区间内部的元素同时加 v相邻差值不变所以中间不用动但 l 位置相对 l-1 位置多了一个 v所以 diff[l] 要加 vr1 位置相对 r 位置也必须回到原来的差值所以 diff[r1] 要减 v。我常用的生活类比是队伍发牌子。想象一列队伍每个人手里有一个数字。你要让连续一段所有人都加上 v。与其一个个通知不如在队首挂一个v的牌子在队尾后一个人那里挂一个-v的牌子。然后让每个人从队首走到队尾边走边累计看到的牌子最终每个人的数字就都对了。diff 数组就是这些牌子的存放处。2.3 完整示例m 次区间加后输出数组看一个可以完整复现的例子。n 5初始数组全 0三次操作[1, 3] 加 2[2, 5] 加 1[3, 4] 加 3先开一个长度 n2 的 diff全 0。依次操作操作1diff[1] 2diff[4] - 2 操作2diff[2] 1diff[6] - 1 操作3diff[3] 3diff[5] - 3最后对 diff 做一遍前缀和diff [2, 1, 3, -2, -3, -1] 前缀和 [2, 3, 6, 4, 1]验证一下第一次后是 [2, 2, 2, 0, 0]第二次后 [2, 3, 3, 1, 1]第三次后 [2, 3, 6, 4, 1]完全一致。完整代码#include bits/stdc.h using namespace std; int main() { int n, m; cin n m; vectorlong long diff(n 2, 0); while (m--) { int l, r; long long v; cin l r v; diff[l] v; diff[r 1] - v; } vectorlong long ans(n 1, 0); for (int i 1; i n; i) { ans[i] ans[i - 1] diff[i]; cout ans[i] (i n ? \n : ); } return 0; }注意 diff 开的是 n 2不是 n 1。因为当 r n 时diff[r 1] diff[n 1]必须保证这个位置存在。这算是老生常谈但真的很多人写错导致越界。2.4 什么时候该用差分什么时候不能硬用差分适合的场景是大量区间修改操作最后只需要输出/查询一次结果。这种离线批量修改是差分的主场。反过来如果你每次修改之后都要立刻查询某个位置的值那一维差分就撑不住了得换树状数组或者线段树做区间加、单点查。差分的 O(1) 修改是把代价推迟到了最后那一次前缀和上并不是真的凭空消失了只是摊还到了最后。3. 二维矩阵前缀和与差分的大显身手之处3.1 二维前缀和的容斥公式一维的前缀和很容易理解到了二维就容易绕。核心是下面这个递推式S[i][j] S[i - 1][j] S[i][j - 1] - S[i - 1][j - 1] a[i][j]记忆法就一句话左 上 - 左上 自己。为什么减左上因为左和上两块都包含左上角那块矩形区域加了两遍所以要扣掉一次。这个操作和集合容斥是同一个道理。有了 S 数组查询左上角 (x1, y1) 到右下角 (x2, y2) 的子矩阵和res S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] S[x1 - 1][y1 - 1]也就是说从右下角的大矩形里减去上方那条减去左方那条再把被重复减掉的左上角加回来。很多文章直接给公式但我觉得这句话值得多读两遍因为面试时手推很容易错。举个例子。3x3 矩阵1 2 3 4 5 6 7 8 9S[3][3] 45。查询 (2,2) 到 (3,3)也就是右下角 2x2 区域手算是 568928。套公式45 - S[1][3] - S[3][1] S[1][1] 45 - 6 - 12 1 28完全一致。这种手算验证特别重要能帮你确认自己有没有把 x2 写成 x1。3.2 二维差分四个端点的魔法二维差分的思路和一维一模一样只是端点从两个变成四个。要让矩形 (x1, y1) 到 (x2, y2) 整体加 v对差分数组 D 做D[x1][y1] v D[x2 1][y1] - v D[x1][y2 1] - v D[x2 1][y2 1] v为什么右下角是加 v 而不是减 v因为在一维差分里区间加 v 要处理尾部后一个位置减 v。二维相当于对每一行做差分同时要考虑列方向的扩散。左上角加了 v 后向下和向右都会传递所以在左边界下方要减在上边界右侧要减但右下角那个点同时被向下减和向右减碰到了两下导致被多减了所以必须加回 v。代码框架int n, m; vectorvectorlong long D(n 2, vectorlong long(m 2, 0)); auto add [](int x1, int y1, int x2, int y2, long long v) { D[x1][y1] v; D[x2 1][y1] - v; D[x1][y2 1] - v; D[x2 1][y2 1] v; }; // 最后做二维前缀和还原 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];看到没有恢复原数组的过程就是二维前缀和的递推式。学的时候把这两个放在一起记事半功倍。3.3 一个典型的网格区域修改题假设有一个 1000×1000 的网格初始全 0要执行 10^5 次操作每次把一个矩形区域加 1最后输出所有格子的值。暴力做法每次操作遍历矩形内部所有格子假设平均面积是 500×500那么总操作量是 10^5 × 2.5×10^5 2.5×10^10必然超时。差分做法每次操作只改四个端点O(1)。所有操作结束后对 D 做一次二维前缀和 O(nm)。总复杂度 O(m nm)在 1000×1000 下完全轻松。对比表格方法单次修改复杂度最后恢复复杂度适用场景暴力O(矩形面积)无操作次数少、网格小二维差分O(1)O(nm)操作次数多、最后一次查询二维树状数组O(log²n)O(1)单点查询修改和查询穿插执行这里要特别强调一个边界二维差分适合先修改、后统一查询的离线场景。如果修改了几次就要立刻查某个点的值再用差分就不合适了。判断的标准永远是查询发生的时间点是在所有修改之后还是穿插在修改中间。4. 树上差分把路径问题变成子树统计问题4.1 为什么树的路径也能做差分数组的区间是一段连续下标但树的路径不是这样。不过树有一个天然优势任意两个点 u 和 v 之间的路径可以拆成 u 到 LCA 和 v 到 LCA 两段。如果我们能在 LCA 处做一些抵消树的路径操作就可以通过端点 LCA几个点的修改来完成最后用一遍 DFS 累加子树得到每一条边或每一个点的覆盖次数。这也是树上差分最经典的应用统计每条边被多少条路径覆盖。假设一共有 m 条路径你当然可以对每条路径暴力走一遍但那样复杂度是 O(m × 路径长度)用树上差分每条路径只做 O(log n) 的 LCA 计算加 O(1) 的端点修改最后 DFS 一遍统计总复杂度变成 O((n m) log n)。实际操作前必须先分清楚两种模式边权差分和点权差分。它们的端点更新方式不一样弄混了结果一定错。4.2 边权差分的端点标记与推导边权差分的目标是统计每条边被覆盖的次数。实现时把每条边看成挂在深度更深的那个子节点上比如父节点 u子节点 v那么边 (u, v) 的覆盖次数就记在 v 这个点上。对于路径操作 (x, y)边权差分的更新是diff[x] v diff[y] v diff[lca] - 2 * v理解方式是先让 x 到根上的每条边都加 v也让 y 到根上的每条边都加 v。这样一来x 到 lca、y 到 lca 这两段路径上的边都被正确加了一次但 lca 到根的那一段边却被加了两次而这段边实际上并不在路径 (x, y) 上。因此在 lca 处减 2v把多余的两份全部消掉。用一个链状例子验证。树是 1 - 2 - 3根是 1对路径 (2, 3) 加 1LCA 是 2。更新diff[2] 1 diff[3] 1 diff[2] - 2 // 所以 diff[2] 总共是 -1DFS 累加子树节点 3 的子树和是 1对应边 (2,3) 被覆盖 1 次节点 2 的子树和是 diff[2] 子树3的和 -1 1 0对应边 (1,2) 被覆盖 0 次。完全正确。4.3 点权差分的差别LCA 的父节点也要动如果目标是统计每个点被覆盖的次数更新方式变成diff[x] v diff[y] v diff[lca] - v diff[fa[lca]] - v这次多了一个 fa[lca]也就是 LCA 的父节点。为什么因为路径 (x, y) 上确实包含 lca 这个点但不包含 lca 上面的任何点。x 到根、y 到根两条链在 lca 处加起来给 lca 算了两次实际只需要一次所以在 lca 处减 v而 lca 以上的点完全不应该被算到所以要在 fa[lca] 处再减 v把向上传递的多余覆盖彻底掐断。还是用链 1 - 2 - 3根是 1路径 (2, 3) 覆盖的点是 2 和 3。LCA 2fa[2] 1。更新diff[2] 1 diff[3] 1 diff[2] - 1 diff[1] - 1得到 diff[1] -1diff[2] 0diff[3] 1。DFS 后每个点的子树累加节点 31节点 2diff[2] 1 1节点 1diff[1] 1 0最后得到覆盖次数点 3 是 1点 2 是 1点 1 是 0完全正确。4.4 完整实现思路和复杂度整体流程可以分成三步预处理树结构任选一个根通常选 1DFS 或 BFS 计算每个点的深度 dep以及倍增数组 anc[k][u]用来 O(log n) 求 LCA。对每条路径操作 (x, y)求出 lca LCA(x, y)然后按照点权或边权模式更新 diff 数组。所有路径处理完后再做一次 DFS从叶子往根累加子树 diff 和每个点的累加值就是该点或该点到父节点的边的覆盖次数。伪代码大概是void dfs_pre(int u, int fa) { dep[u] dep[fa] 1; anc[0][u] fa; for (int k 1; k LOG; k) anc[k][u] anc[k - 1][anc[k - 1][u]]; for (int v : g[u]) { if (v fa) continue; dfs_pre(v, u); } } void dfs_calc(int u, int fa) { for (int v : g[u]) { if (v fa) continue; dfs_calc(v, u); sum[u] sum[v]; } sum[u] diff[u]; // 点权模式这里是节点覆盖次数边权模式如果边挂在节点上同理 }复杂度方面LCA 的倍增预处理是 O(n log n)每条路径一次 LCA O(log n)最后 DFS O(n)总复杂度 O((n m) log n)。这个复杂度在树上路径统计题里是标准配置。4.5 经典应用找被覆盖次数最多的边很多竞赛题都能抽象成这个问题给定一棵 n 个点的树和 m 条路径问哪条边被路径覆盖的次数最多或者是否存在一条边被所有路径覆盖。用边权差分做就非常顺手每条路径在 diff 上做端点更新最后 DFS 统计每个点对应父边的覆盖次数顺手取 max。类似的点权版本城市公交线路问题m 条线路各自覆盖树上连续一段站点统计每个站点被多少条线路经过。把站点当作节点线路当作路径直接用点权差分一次 DFS 就能出结果。树上差分的两个关键点一定要记牢第一diff 更新的目标是谁取决于你要统计边还是统计点第二后处理的 DFS 累加方向是从叶子到根不是从根到叶子。方向反了整个结果就是乱的。5. 实战过程中我踩过的坑以及可复用的排错思路5.1 下标错位是最隐蔽的错误之一前缀和和差分这套技巧代码本身都短得不能再短所以一旦结果不对90% 的情况是下标错位。最常见的有两种一是从 0-indexed 的输入转成 1-indexed 的 diff 时忘了统一二是做二维差分时把 x2 1 和 y2 1 写反了位置。我现在的习惯是只要涉及前缀和、差分一律开局就声明数组大小 n 2 或者 (n 2) x (m 2)不要吝啬这一点空间。多两个位置换来的不只是安全也是心理上的省心。5.2 int 溢出和 long long 的选用前缀和累加的数值非常容易超过 int。举个例子a[i] 的范围是 1e9n 是 1e5那么 pre[n] 最大能到 1e14int 早就爆了。二维前缀和更容易炸因为累加的是整个矩形面积。我的经验是只要题目里数组元素值域超过 1e5或者操作次数超过 1e5前缀和与差分的数组一律开 long long。别为了省一点内存去用 int最后排查溢出问题才是最痛苦的事。5.3 二维差分边界越界二维差分的 add 函数里要写 D[x2 1][y2 1]当 x2 n 或 y2 m 时就会访问到 n 1 或 m 1。如果数组开成 n x m这里直接越界跑飞。解决方式很简单统一开成 (n 2) x (m 2)。在某些语言里越界可能不报错但你后续前缀和算出来的结果会莫名多出很多怪值排查起来更头疼。5.4 树上差分结果不对优先怀疑 LCA树上差分的端点更新完全依赖 LCA 的正确性。如果你发现覆盖次数整体对不上先别急着怀疑 diff 的更新公式而是用一个简单样例验证 LCA。我常用的验证样例是链状树和星形树。链状树能测出 LCA 深度处理是否正确星形树能测出根节点和祖先边界。常见错误包括倍增数组的大小开小了anc[0][root] 没有设置成 rootdep 数组的计算顺序写反了。问题逐个排除后再回头检查 diff 端点是边权模式还是点权模式。5.5 别被差分这个词带偏搜索差分相关内容时你会看到一堆完全不同的概念差分放大电路、差分信号线、差分隐私、差分方程、差分约束系统。它们和算法里的差分数组并不是一回事。本文讨论的差分核心是用相邻元素的差值记录变化量再通过前缀和还原差分方程是数学里的递推关系差分约束系统是图论里通过最短路求不等式组解的问题。初学者看到这些概念时不用慌先判断所在领域再决定要不要深入。至少在我说的算法场景里前缀和与差分就是一对互逆操作没有更复杂的含义。一点个人的学习习惯最后分享一个小技巧每次遇到区间修改、区间查询的题目我会先在纸上画一条一维的轴把左端点和右端点标出来想想能不能转成两个端点的标记。这个习惯帮我解决了很多看起来跟差分无关的题比如某些扫描线问题、某些双数组交叉增减的问题。如果你刚开始学建议按一维数组 - 二维矩阵 - 树上的顺序刷每个例子都拿笔算一遍再上机验证。前缀和与差分单独看都很简单但把它们当成一对互逆操作来理解时很多复杂问题会突然变得规整。
前缀和与差分：从一维区间操作到二维矩阵与树上差分
如果你刷过算法题或者哪怕只是在业务代码里处理过时间序列、累计统计这类需求应该对下面这个场景不陌生一个长度为 n 的数组内存完全放得下但你要反复做区间操作——要么问 sum(l,r)要么把区间 l..r 同时加一个数。第一时间想到的往往是 for 循环可当 n 和 m 都到 10^5 甚至 10^6 时最坏情况就是 10^10 次运算比赛和面试基本都稳挂。其实这两个高频问题分别对应两个极其基础的工具前缀和和差分。前缀和把区间求和变成两个前缀和的减法差分把区间加法变成两个端点上的标记而且它们互为逆运算——一个是累计一个是差值。这篇文章我就从零开始把这套东西讲透覆盖一维、二维矩阵和树上场景最后把我在实战中踩过的坑一并列出来。1. 前缀和把区间查询从 O(n) 降到 O(1)1.1 前缀和的本质是一本流水账设原数组 a下标从 1 开始。前缀和数组 pre[i] 表示 a[1] 累加到 a[i] 的总和递推式只有一条pre[i] pre[i - 1] a[i]求区间 [l, r] 的和直接用 pre[r] - pre[l - 1]。为什么它能成立我习惯把它理解成一本流水账a 是每天的花销pre[i] 是到第 i 天为止的累计花销。要问第 l 天到第 r 天总共花了多少用前 r 天的累计减去前 l-1 天的累计中间那一截自然就出来了。这里依赖的数学性质其实只有加法结合律和减法还原所以它非常稳定。你可能会想这有什么难的但前缀和真正的价值在于复杂度。预处理一遍 O(n)之后每次区间查询都是 O(1)。如果查询次数是 m暴力做就是 O(nm)前缀和变成 O(n m)。当 n 和 m 都在 10^5 这个量级时差距是千万级别到毫秒级别的差距。我常说生活中的余额就是一个前缀和模型。银行不会为每笔转账单独记住流水段它只记录每个时刻的余额你要某段时间的明细把余额相减再配合筛选就行。一旦你意识到累计量能被减法还原出区间量很多问题的第一步就清晰了。1.2 代码实现里的下标细节先看最标准的实现。C 版本#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorlong long a(n 1, 0), pre(n 1, 0); for (int i 1; i n; i) { cin a[i]; pre[i] pre[i - 1] a[i]; } auto query [](int l, int r) { return pre[r] - pre[l - 1]; }; // 示例查询区间 [2, 4] cout query(2, 4) endl; return 0; }Python 版本也很简单n int(input()) a [0] list(map(int, input().split())) pre [0] * (n 1) for i in range(1, n 1): pre[i] pre[i - 1] a[i] def query(l, r): return pre[r] - pre[l - 1] print(query(2, 4))很多新手最容易栽在下标上。我的建议是只要写前缀和一律让数组下标从 1 开始把下标 0 空出来。这样 query(l, r) 里的 pre[l - 1] 永远不会访问到负下标代码逻辑也不用为 l 1 单独写分支。如果你非要坚持 0-indexed那要注意你的查询区间很可能变成左闭右开 [l, r)也就是 pre[r] - pre[l]两个模型千万别混用。1.3 前缀思想不只是求和前缀和最常见的进阶玩法是前缀异或。把加法换成异或得到 preXor[i] preXor[i - 1] ^ a[i]区间异或结果就是 preXor[r] ^ preXor[l - 1]。原理是异或两次同一个数会抵消和加法减法是同一个逻辑。前缀积也能做但在取模场景下要配合逆元区间积等于 preMul[r] 乘上 preMul[l - 1] 的逆元。如果只是普通整数直接相除就行不过要注意除零和溢出问题。还有一个非常高频的面试题变形统计和等于 k 的连续子数组个数。暴力是 O(n^2)但用前缀和配合哈希表可以做到 O(n)。核心思路是遍历到位置 j 时前缀和为 pre[j]如果之前某个位置 i 的前缀和 pre[i] 等于 pre[j] - k那么 (i1) 到 j 这一段的和就是 k。于是问题变成了统计 pre[i] 出现的次数一个哈希表就搞定了。不过需要提醒一个边界前缀最大值、前缀最小值这种是不能用两个前缀做差来还原任意区间最值的因为最值运算不可逆。遇到区间最值题目别硬套前缀和老老实实走线段树或者 ST 表。2. 差分把区间修改从 O(n) 降到 O(1)2.1 差分数组到底存了什么如果说前缀和记录的是累计状态那差分数组记录的就是变化量。定义很简单diff[i] a[i] - a[i - 1]其中约定 a[0] 0所以 diff[1] a[1]。你会发现一个有趣的事实对 diff 数组求前缀和恰好能还原出原数组 a。也就是说a 是 diff 的前缀和数组。这两个概念就像照镜子一样前缀和是正着看差分是反着看。用个具体例子。a [2, 5, 9, 1, 4]那么diff[1] 2 diff[2] 5 - 2 3 diff[3] 9 - 5 4 diff[4] 1 - 9 -8 diff[5] 4 - 1 3对 diff 累加2 3 4 - 8 3 4正好是 a[5]。这就是差分和前缀和互逆的最直观体现。2.2 区间加一次操作就这么点东西现在问题是给区间 [l, r] 整体加 v差分数组要怎么改答案是两句diff[l] v diff[r 1] - v为什么两个端点就够了因为差分描述的是相邻元素的差值。区间内部的元素同时加 v相邻差值不变所以中间不用动但 l 位置相对 l-1 位置多了一个 v所以 diff[l] 要加 vr1 位置相对 r 位置也必须回到原来的差值所以 diff[r1] 要减 v。我常用的生活类比是队伍发牌子。想象一列队伍每个人手里有一个数字。你要让连续一段所有人都加上 v。与其一个个通知不如在队首挂一个v的牌子在队尾后一个人那里挂一个-v的牌子。然后让每个人从队首走到队尾边走边累计看到的牌子最终每个人的数字就都对了。diff 数组就是这些牌子的存放处。2.3 完整示例m 次区间加后输出数组看一个可以完整复现的例子。n 5初始数组全 0三次操作[1, 3] 加 2[2, 5] 加 1[3, 4] 加 3先开一个长度 n2 的 diff全 0。依次操作操作1diff[1] 2diff[4] - 2 操作2diff[2] 1diff[6] - 1 操作3diff[3] 3diff[5] - 3最后对 diff 做一遍前缀和diff [2, 1, 3, -2, -3, -1] 前缀和 [2, 3, 6, 4, 1]验证一下第一次后是 [2, 2, 2, 0, 0]第二次后 [2, 3, 3, 1, 1]第三次后 [2, 3, 6, 4, 1]完全一致。完整代码#include bits/stdc.h using namespace std; int main() { int n, m; cin n m; vectorlong long diff(n 2, 0); while (m--) { int l, r; long long v; cin l r v; diff[l] v; diff[r 1] - v; } vectorlong long ans(n 1, 0); for (int i 1; i n; i) { ans[i] ans[i - 1] diff[i]; cout ans[i] (i n ? \n : ); } return 0; }注意 diff 开的是 n 2不是 n 1。因为当 r n 时diff[r 1] diff[n 1]必须保证这个位置存在。这算是老生常谈但真的很多人写错导致越界。2.4 什么时候该用差分什么时候不能硬用差分适合的场景是大量区间修改操作最后只需要输出/查询一次结果。这种离线批量修改是差分的主场。反过来如果你每次修改之后都要立刻查询某个位置的值那一维差分就撑不住了得换树状数组或者线段树做区间加、单点查。差分的 O(1) 修改是把代价推迟到了最后那一次前缀和上并不是真的凭空消失了只是摊还到了最后。3. 二维矩阵前缀和与差分的大显身手之处3.1 二维前缀和的容斥公式一维的前缀和很容易理解到了二维就容易绕。核心是下面这个递推式S[i][j] S[i - 1][j] S[i][j - 1] - S[i - 1][j - 1] a[i][j]记忆法就一句话左 上 - 左上 自己。为什么减左上因为左和上两块都包含左上角那块矩形区域加了两遍所以要扣掉一次。这个操作和集合容斥是同一个道理。有了 S 数组查询左上角 (x1, y1) 到右下角 (x2, y2) 的子矩阵和res S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] S[x1 - 1][y1 - 1]也就是说从右下角的大矩形里减去上方那条减去左方那条再把被重复减掉的左上角加回来。很多文章直接给公式但我觉得这句话值得多读两遍因为面试时手推很容易错。举个例子。3x3 矩阵1 2 3 4 5 6 7 8 9S[3][3] 45。查询 (2,2) 到 (3,3)也就是右下角 2x2 区域手算是 568928。套公式45 - S[1][3] - S[3][1] S[1][1] 45 - 6 - 12 1 28完全一致。这种手算验证特别重要能帮你确认自己有没有把 x2 写成 x1。3.2 二维差分四个端点的魔法二维差分的思路和一维一模一样只是端点从两个变成四个。要让矩形 (x1, y1) 到 (x2, y2) 整体加 v对差分数组 D 做D[x1][y1] v D[x2 1][y1] - v D[x1][y2 1] - v D[x2 1][y2 1] v为什么右下角是加 v 而不是减 v因为在一维差分里区间加 v 要处理尾部后一个位置减 v。二维相当于对每一行做差分同时要考虑列方向的扩散。左上角加了 v 后向下和向右都会传递所以在左边界下方要减在上边界右侧要减但右下角那个点同时被向下减和向右减碰到了两下导致被多减了所以必须加回 v。代码框架int n, m; vectorvectorlong long D(n 2, vectorlong long(m 2, 0)); auto add [](int x1, int y1, int x2, int y2, long long v) { D[x1][y1] v; D[x2 1][y1] - v; D[x1][y2 1] - v; D[x2 1][y2 1] v; }; // 最后做二维前缀和还原 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];看到没有恢复原数组的过程就是二维前缀和的递推式。学的时候把这两个放在一起记事半功倍。3.3 一个典型的网格区域修改题假设有一个 1000×1000 的网格初始全 0要执行 10^5 次操作每次把一个矩形区域加 1最后输出所有格子的值。暴力做法每次操作遍历矩形内部所有格子假设平均面积是 500×500那么总操作量是 10^5 × 2.5×10^5 2.5×10^10必然超时。差分做法每次操作只改四个端点O(1)。所有操作结束后对 D 做一次二维前缀和 O(nm)。总复杂度 O(m nm)在 1000×1000 下完全轻松。对比表格方法单次修改复杂度最后恢复复杂度适用场景暴力O(矩形面积)无操作次数少、网格小二维差分O(1)O(nm)操作次数多、最后一次查询二维树状数组O(log²n)O(1)单点查询修改和查询穿插执行这里要特别强调一个边界二维差分适合先修改、后统一查询的离线场景。如果修改了几次就要立刻查某个点的值再用差分就不合适了。判断的标准永远是查询发生的时间点是在所有修改之后还是穿插在修改中间。4. 树上差分把路径问题变成子树统计问题4.1 为什么树的路径也能做差分数组的区间是一段连续下标但树的路径不是这样。不过树有一个天然优势任意两个点 u 和 v 之间的路径可以拆成 u 到 LCA 和 v 到 LCA 两段。如果我们能在 LCA 处做一些抵消树的路径操作就可以通过端点 LCA几个点的修改来完成最后用一遍 DFS 累加子树得到每一条边或每一个点的覆盖次数。这也是树上差分最经典的应用统计每条边被多少条路径覆盖。假设一共有 m 条路径你当然可以对每条路径暴力走一遍但那样复杂度是 O(m × 路径长度)用树上差分每条路径只做 O(log n) 的 LCA 计算加 O(1) 的端点修改最后 DFS 一遍统计总复杂度变成 O((n m) log n)。实际操作前必须先分清楚两种模式边权差分和点权差分。它们的端点更新方式不一样弄混了结果一定错。4.2 边权差分的端点标记与推导边权差分的目标是统计每条边被覆盖的次数。实现时把每条边看成挂在深度更深的那个子节点上比如父节点 u子节点 v那么边 (u, v) 的覆盖次数就记在 v 这个点上。对于路径操作 (x, y)边权差分的更新是diff[x] v diff[y] v diff[lca] - 2 * v理解方式是先让 x 到根上的每条边都加 v也让 y 到根上的每条边都加 v。这样一来x 到 lca、y 到 lca 这两段路径上的边都被正确加了一次但 lca 到根的那一段边却被加了两次而这段边实际上并不在路径 (x, y) 上。因此在 lca 处减 2v把多余的两份全部消掉。用一个链状例子验证。树是 1 - 2 - 3根是 1对路径 (2, 3) 加 1LCA 是 2。更新diff[2] 1 diff[3] 1 diff[2] - 2 // 所以 diff[2] 总共是 -1DFS 累加子树节点 3 的子树和是 1对应边 (2,3) 被覆盖 1 次节点 2 的子树和是 diff[2] 子树3的和 -1 1 0对应边 (1,2) 被覆盖 0 次。完全正确。4.3 点权差分的差别LCA 的父节点也要动如果目标是统计每个点被覆盖的次数更新方式变成diff[x] v diff[y] v diff[lca] - v diff[fa[lca]] - v这次多了一个 fa[lca]也就是 LCA 的父节点。为什么因为路径 (x, y) 上确实包含 lca 这个点但不包含 lca 上面的任何点。x 到根、y 到根两条链在 lca 处加起来给 lca 算了两次实际只需要一次所以在 lca 处减 v而 lca 以上的点完全不应该被算到所以要在 fa[lca] 处再减 v把向上传递的多余覆盖彻底掐断。还是用链 1 - 2 - 3根是 1路径 (2, 3) 覆盖的点是 2 和 3。LCA 2fa[2] 1。更新diff[2] 1 diff[3] 1 diff[2] - 1 diff[1] - 1得到 diff[1] -1diff[2] 0diff[3] 1。DFS 后每个点的子树累加节点 31节点 2diff[2] 1 1节点 1diff[1] 1 0最后得到覆盖次数点 3 是 1点 2 是 1点 1 是 0完全正确。4.4 完整实现思路和复杂度整体流程可以分成三步预处理树结构任选一个根通常选 1DFS 或 BFS 计算每个点的深度 dep以及倍增数组 anc[k][u]用来 O(log n) 求 LCA。对每条路径操作 (x, y)求出 lca LCA(x, y)然后按照点权或边权模式更新 diff 数组。所有路径处理完后再做一次 DFS从叶子往根累加子树 diff 和每个点的累加值就是该点或该点到父节点的边的覆盖次数。伪代码大概是void dfs_pre(int u, int fa) { dep[u] dep[fa] 1; anc[0][u] fa; for (int k 1; k LOG; k) anc[k][u] anc[k - 1][anc[k - 1][u]]; for (int v : g[u]) { if (v fa) continue; dfs_pre(v, u); } } void dfs_calc(int u, int fa) { for (int v : g[u]) { if (v fa) continue; dfs_calc(v, u); sum[u] sum[v]; } sum[u] diff[u]; // 点权模式这里是节点覆盖次数边权模式如果边挂在节点上同理 }复杂度方面LCA 的倍增预处理是 O(n log n)每条路径一次 LCA O(log n)最后 DFS O(n)总复杂度 O((n m) log n)。这个复杂度在树上路径统计题里是标准配置。4.5 经典应用找被覆盖次数最多的边很多竞赛题都能抽象成这个问题给定一棵 n 个点的树和 m 条路径问哪条边被路径覆盖的次数最多或者是否存在一条边被所有路径覆盖。用边权差分做就非常顺手每条路径在 diff 上做端点更新最后 DFS 统计每个点对应父边的覆盖次数顺手取 max。类似的点权版本城市公交线路问题m 条线路各自覆盖树上连续一段站点统计每个站点被多少条线路经过。把站点当作节点线路当作路径直接用点权差分一次 DFS 就能出结果。树上差分的两个关键点一定要记牢第一diff 更新的目标是谁取决于你要统计边还是统计点第二后处理的 DFS 累加方向是从叶子到根不是从根到叶子。方向反了整个结果就是乱的。5. 实战过程中我踩过的坑以及可复用的排错思路5.1 下标错位是最隐蔽的错误之一前缀和和差分这套技巧代码本身都短得不能再短所以一旦结果不对90% 的情况是下标错位。最常见的有两种一是从 0-indexed 的输入转成 1-indexed 的 diff 时忘了统一二是做二维差分时把 x2 1 和 y2 1 写反了位置。我现在的习惯是只要涉及前缀和、差分一律开局就声明数组大小 n 2 或者 (n 2) x (m 2)不要吝啬这一点空间。多两个位置换来的不只是安全也是心理上的省心。5.2 int 溢出和 long long 的选用前缀和累加的数值非常容易超过 int。举个例子a[i] 的范围是 1e9n 是 1e5那么 pre[n] 最大能到 1e14int 早就爆了。二维前缀和更容易炸因为累加的是整个矩形面积。我的经验是只要题目里数组元素值域超过 1e5或者操作次数超过 1e5前缀和与差分的数组一律开 long long。别为了省一点内存去用 int最后排查溢出问题才是最痛苦的事。5.3 二维差分边界越界二维差分的 add 函数里要写 D[x2 1][y2 1]当 x2 n 或 y2 m 时就会访问到 n 1 或 m 1。如果数组开成 n x m这里直接越界跑飞。解决方式很简单统一开成 (n 2) x (m 2)。在某些语言里越界可能不报错但你后续前缀和算出来的结果会莫名多出很多怪值排查起来更头疼。5.4 树上差分结果不对优先怀疑 LCA树上差分的端点更新完全依赖 LCA 的正确性。如果你发现覆盖次数整体对不上先别急着怀疑 diff 的更新公式而是用一个简单样例验证 LCA。我常用的验证样例是链状树和星形树。链状树能测出 LCA 深度处理是否正确星形树能测出根节点和祖先边界。常见错误包括倍增数组的大小开小了anc[0][root] 没有设置成 rootdep 数组的计算顺序写反了。问题逐个排除后再回头检查 diff 端点是边权模式还是点权模式。5.5 别被差分这个词带偏搜索差分相关内容时你会看到一堆完全不同的概念差分放大电路、差分信号线、差分隐私、差分方程、差分约束系统。它们和算法里的差分数组并不是一回事。本文讨论的差分核心是用相邻元素的差值记录变化量再通过前缀和还原差分方程是数学里的递推关系差分约束系统是图论里通过最短路求不等式组解的问题。初学者看到这些概念时不用慌先判断所在领域再决定要不要深入。至少在我说的算法场景里前缀和与差分就是一对互逆操作没有更复杂的含义。一点个人的学习习惯最后分享一个小技巧每次遇到区间修改、区间查询的题目我会先在纸上画一条一维的轴把左端点和右端点标出来想想能不能转成两个端点的标记。这个习惯帮我解决了很多看起来跟差分无关的题比如某些扫描线问题、某些双数组交叉增减的问题。如果你刚开始学建议按一维数组 - 二维矩阵 - 树上的顺序刷每个例子都拿笔算一遍再上机验证。前缀和与差分单独看都很简单但把它们当成一对互逆操作来理解时很多复杂问题会突然变得规整。