差分数组完全解析：原理、模板与实战应用

差分数组这东西说简单也简单说容易出错也真容易出错。它跟前缀和是一对“逆运算”关系理解好了能帮你在区间修改、区间覆盖、多次操作后统一查询这类问题上省下大量时间。我在实际刷题和写代码时用过很多次尤其遇到“给定多次区间操作最后统一问结果”的场景差分数组几乎是标准解法。这篇算是对差分数组的一个补充整理把原理、构造、实战套路和踩过的坑一并讲透适合算法初学者、准备面试的开发者以及比赛前想快速过一遍基础技巧的人。1. 为什么需要差分数组从朴素做法到底层优化1.1 每次区间操作都遍历到底有多亏先看一类最常见的需求给定一个长度为 n 的数组初始值都是 0现在有 m 次操作每次操作把区间[L, R]内的所有元素加上一个值v。所有操作完成后问最终数组长什么样。最朴素的做法当然是一次一次来每次操作都 for 循环从 L 遍历到 R把每个元素加上 v。这样单次操作的时间复杂度是 O(R - L 1)最坏情况是 O(n)m 次操作就是 O(nm)。当 n 和 m 都来到 10^5 甚至 10^6 级别时这个复杂度是绝对跑不完的。有人可能会说那我用线段树或者树状数组不就行了确实可以但这两个数据结构都有一定实现成本而且在这个“只做区间加、最后统一查询”的场景里它们属于“杀鸡用了牛刀”。差分数组只用一次 O(n) 的预处理加 m 次 O(1) 的修改最后再 O(n) 还原结果整体复杂度 O(n m)无论是代码量还是运行速度都占优。1.2 差分数组的数学本质把区间修改变成单点修改差分数组的核心思想非常朴素我不直接维护原始数组本身而是维护“相邻元素之间的差值”。具体来说对于原始数组a[0..n-1]这里先用 0 下标举例定义差分数组d[0..n-1]其中d[0] a[0] d[i] a[i] - a[i-1] (i 1)这个定义有一个特别好的性质如果我们对差分数组做前缀和也就是按顺序累加d[0] d[1] ... d[i]得到的恰好就是a[i]。这个性质的价值在于对原数组进行区间加[L, R]加 v反映到差分数组上只需要修改两个位置。因为区间内部的相邻差值没有变化只有边界位置的差值会突变。具体来说d[L] v if (R 1 n) d[R 1] - v这背后的直觉你可以这么理解你在一个从 L 到 R 的连续区间内统一提高 v相当于在这个区间的“入口处”加上了 v 的增量在“出口之后”再把这部分增量减掉这样区间外的元素就不会被影响。所有区间修改都转成两个单点修改这就是差分数组能提速的根本原因。2. 差分数组的构造、更新与还原手把手拆解2.1 三种初始化方式对应不同场景构造差分数组有几种写法我按使用场景分开说第一种已经给出了原始数组需要构造它的差分数组。这是最直接的// C数组下标从 0 开始 vectorint a {1, 3, 5, 2, 7}; // 原始数组 int n a.size(); vectorint d(n, 0); d[0] a[0]; for (int i 1; i n; i) { d[i] a[i] - a[i-1]; }第二种初始数组全都是 0只有若干次区间加操作。这时你甚至不需要建原始数组直接建立一个长度为 n 的全零差分数组每次操作只在两个端点做修改最后再前缀和还原即可。这种场景最常见代码也是最简洁的vectorint d(n, 0); // 每次操作 [L, R] 加 v d[L] v; if (R 1 n) d[R 1] - v; // 最后还原 vectorint res(n, 0); int cur 0; for (int i 0; i n; i) { cur d[i]; res[i] cur; }第三种也是很多教程里默认的写法数组下标从 1 开始。这种写法在某些题目里可以避免像R 1越界的判断尤其是配合前缀和、树状数组时从 1 开始的下标会让边界处理更统一。// 下标从 1 开始n 为实际元素个数数组开 n2 或更大 vectorint d(n 2, 0); // 每次操作 [L, R] 加 v d[L] v; d[R 1] - v; // 因为多开了一个位置这里不会越界最后遍历到 n 即可 // 还原 for (int i 1; i n; i) { d[i] d[i-1]; // 此时 d[i] 就是最终数组第 i 个位置的值 }我个人习惯在解题时优先用下标从 1 开始的方式因为省去了R 1 n这种边界判断代码出错概率更低。缺点是要记住 array 的实际存储范围不能搞混循环边界。2.2 核心代码实现区间更新为什么只改两个点前面已经提到区间更新只需要修改两个位置。这里我用一个具体例子把全过程走一遍帮助你彻底理解它为什么是对的。假设初始数组长度为 8全部是 0。现在做两次操作操作 1区间[2, 5]加 3操作 2区间[4, 6]加 2按差分的写法初始差分数组 d 全为 0操作 1 后d[2] 3 d[6] - 3操作 2 后d[4] 2 d[7] - 2此时差分数组为下标: 0 1 2 3 4 5 6 7 d: 0 0 3 0 2 0 -3 -2然后做前缀和得到原数组i0: 0 i1: 0 i2: 03 3 i3: 030 3 i4: 0302 5 i5: 03020 5 i6: 030200 5 i7: 030200-3 2所以最终数组是[0, 0, 3, 3, 5, 5, 5, 2]。你自己验证一下区间[2,5]加 3区间[4,6]加 2叠加效果就是下标 2~3 为 34~5 为 56 为 2跟结果完全一致。注意一个细节操作 2 的区间[4, 6]加 2和操作 1 的区间[2, 5]有重叠部分[4, 5]。差分数组天然处理了这种多次叠加不需要额外判断重叠逻辑每个区间的修改都是独立的最终前缀和把它们的贡献累加起来。这也是差分数组在“多次区间覆盖”问题上特别方便的原因。2.3 差分与前缀和的耦合还原阶段的一个小工具上面还原阶段其实就是对差分数组求前缀和。很多初学者会把前缀和和差分搞混这里再区分一下前缀和数组prefix[i] a[0] a[1] ... a[i]用来快速求解静态区间和。差分数组d[i] a[i] - a[i-1]是前缀和的逆运算用来快速处理区间修改。它们互为逆操作对差分数组求前缀和能得到原数组对原数组求前缀和能得到前缀和数组。实际解题时两者还能结合使用。比如有些题目要求“多次区间加之后频繁查询某个区间的和”这时可以先用差分处理所有区间修改再一次性求得最终数组然后用前缀和对最终数组做静态查询。整个过程相当于“先差分后前缀和”两道工序配合起来非常流畅。3. 差分数组的高阶应用二维差分与联合套路3.1 二维差分矩阵区间加思路完全一脉相承差分数组的思想可以扩展到二维矩阵。给定一个n x m的全零矩阵进行若干次“子矩阵加 v”的操作最后求矩阵每个位置的值。朴素做法每次 O(n*m)二维差分可以把单次操作降到 O(1)。二维差分的定义稍微复杂一点核心同样是维护“差值矩阵”。设d[i][j]为二维差分矩阵当我们要对左上角(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再利用二维前缀和还原即对每个元素d[i][j] d[i-1][j] d[i][j-1] - d[i-1][j-1]得到的d[i][j]就是原矩阵中该位置的值。四个位置里最后一个v比较容易被忽略但它是二维差分能否正确的关键。你可以这么理解第一个v让子矩阵左上角产生增量第二、第三个-v分别把下方和右侧的增量抵消掉但这样右下角被减了两遍所以要再加一次 v 回补。这个逻辑跟“矩形面积交叠”里的容斥原理很像。3.2 差分数组与贪心、二分的经典组合差分数组最常用的进阶套路有两个一个是配合二分答案一个是配合贪心排序。配合二分答案的场景长这样题目问你“至少需要多少次操作才能满足所有条件”“能否在某个限制内完成全部区间更新”之类答案是单调的可以二分答案。每次二分到一个候选值需要快速验证——这时就用差分数组把当前方案下所有区间的累积效果算出来再逐项检查。因为每次验证只需要 O(n) 的还原时间整体复杂度是 O(n log K)能跑过很大范围的数据。配合贪心排序的场景也不少见尤其是“区间覆盖”“最大重叠点数”这类问题。比如有一堆区间每个区间对点贡献 1问哪个点被覆盖的次数最多。把所有区间的差分处理后一次性还原再扫描找最大值即可。LeetCode 上那道“航班预订统计”本质上就是问每个站点的累计预订量差分数组是标准解法。3.3 树状数组、线段树之外什么时候选差分什么时候不选差分数组不是万能的。它只适用于“所有操作执行完毕后才需要结果”的场景或者说“离线查询”场景。如果每次区间修改之后马上需要查询某个点的值或某个区间的和那差分数组就不适用了因为单次查询需要 O(n) 还原太慢。这时一般有两个选择如果需要动态单点查询同时支持区间修改用树状数组加区间更新单点查询技巧差分数组配合树状数组。实际上树状数组里常见的“区间加、单点查”就是差分的思路只是用树状数组维护差分数组从而能支持 O(log n) 的动态修改和查询。如果需要动态区间求和同时支持区间修改用线段树或带 lazy tag 的树状数组。一句话总结选择标准如果所有操作都在查询之前优先差分数组如果有在线查询需求才需要树状数组或线段树。4. 实战题解用差分数组秒杀三道经典题4.1 LeetCode 1109「航班预订统计」面向结果的区间加这是我在面试中见过很多次的题很多人的第一反应是用双重循环暴力累加然后超时。题目给了 n 个航班和一组预订记录bookings[i] [first, last, seats]表示从第 first 站到第 last 站每一站都增加 seats 个预订量。最终返回每个航班的预订总数。这几乎就是差分数组的模板题。不过有个小细节题目中航班编号从 1 开始而返回数组下标从 0 开始。如果用下标从 0 开始的差分数组需要注意把 first 和 last 都减 1同时last是闭区间所以要在last的位置加 v在last 1的位置减 v。def corpFlightBookings(self, bookings: List[List[int]], n: int) - List[int]: diff [0] * (n 1) for first, last, seats in bookings: diff[first - 1] seats diff[last] - seats res [] cur 0 for i in range(n): cur diff[i] res.append(cur) return res这里把差分数组长度开成 n 1这样当last n时diff[last]不会越界但是还原时只用到前 n 个元素最后一个位置的值只用于抵消不参与最终结果。这个小技巧在写 Python 时特别省心。4.2 LeetCode 370「区间加法」最纯粹的差分模板这题是 LintCode/LeetCode 上的经典模板题题目本身很简单给一个长度为 n 的数组初始为 0给定若干操作每个操作是[start, end, inc]把所有start到end下标之间的元素加 inc返回最终数组。解题思路跟上面几乎一样不同的只是下标是否减一。我拿这题想强调的是用差分数组时更新操作本身只有两行代码剩下的事项都在于边界和还原逻辑是否写对如果end 1可能越界要么在更新时判断要么把数组多开一位。还原时不要忘了从前往后累加。4.3 LeetCode 1589「所有排列中的最大和」差分数组配合贪心这道题的题面是给一个数组 nums 和若干查询区间允许你对 nums 做任意排列要让所有区间内元素之和的总和最大化。思路其实很清晰每个位置被区间覆盖的次数越多就应该放越大的数。所以我们的任务就变成先统计每个位置被多少个区间覆盖然后把最大的数放在覆盖次数最多的位置。统计每个位置的覆盖次数最高效的方法就是差分数组。先用差分数组扫描所有区间每个区间[l, r]让diff[l]、diff[r1]--最后前缀和还原得到每个位置的覆盖频次。之后排序频次数组和 nums反向相乘后累加即可。这道题的意义在于展示了差分数组不只是“区间加”的专属工具任何形式的区间增量统计加 1、加 v、加权重都可以用同一套思路处理。区间重叠次数、覆盖点数、累计在线人数这类问题本质都是差分数组的应用场景。5. 常见问题与排查技巧实录5.1 差分数组下笔前必须想清楚的三个边界先列一下我在实际写代码时反复踩过的坑基本都是边界问题。闭区间还是开区间。题目给的区间是包含左右端点闭区间还是包含左不包含右左闭右开差分数组的修改方式会不一样。闭区间是diff[L] v; diff[R 1] - v;左闭右开是diff[L] v; diff[R] - v;。做题前先明确区间的定义再决定R后面要不要加一。下标从 0 开始还是从 1 开始。很多题目为了方便描述区间编号从 1 开始但数组下标从 0 开始比如航班预订那道题。如果你用的是 0 下标差分数组记得把 L 和 R 都相应减一。差分数组的长度应该开多少。如果还原时要访问到R 1数组长度至少要n 1如果用下标从 1 开始的写法阶数组长度建议开n 2这样R 1最大为n 1也能安全访问到。5.2 为什么我更新了差分数组结果却全错了一个很典型的错误是写了差分数组的更新代码但在还愿时没有按正确的方向累加或者重复累加了多次。比如有人会在还原时写成res[i] diff[i] res[i1]这就反了。差分数组的定义是相邻元素的差所以还原必须从前往后累加这是前缀和的方向不是后缀和的方向。还有一个常见错误是构建差分数组时没有基于初始数组而初始数组并不是全零。如果你拿到一个非零初始数组然后直接用差分做区间加需要先把初始数组转成差分数组再进行区间修改。不能直接把diff初始化为 0然后只处理区间加部分否则初始值会丢失。正确的思路是分成两步// 先把原始数组构建成差分数组 diff[0] a[0]; for (int i 1; i n; i) { diff[i] a[i] - a[i-1]; } // 再执行区间修改 diff[L] v; if (R 1 n) diff[R 1] - v; // 最后前缀和还原5.3 数据溢出的隐蔽风险差分数组里存的是差值如果原始数据范围很大或者区间加的累加次数很多中间值可能超出 int 范围。尤其在做二维差分时四个位置的增量在一轮前缀和中反复叠加溢出的概率更高。我的习惯是只要 n 和操作次数任一可能超过 10^5或者数值范围可能到达 10^9 级别就直接用 long longPython 无所谓但 C/Java 要小心。这不算过度设计因为溢出 bug 一旦出现极其隐蔽调试成本远超写一个 long long 的成本。6. 差分数组的延伸思维从一维到树上差分数组的思想并不局限于数组。它还可以推广到树上形成“树上差分”这是很多算法竞赛中处理树上路径修改问题的利器。树上路径修改的典型场景是给从节点 u 到节点 v 的路径上的所有节点或边加上一个值最后询问每个节点或边被加了多少次。朴素做法走一遍路径是 O(n) 的使用树上差分配合 LCA最近公共祖先可以把单次修改降到 O(1)。树上差分的基本规则是对节点 u 和 v 之间的路径上所有节点加 v则修改diff[u] v、diff[v] v、diff[lca] - v如果是边权还要在diff[parent(lca)] - v。最后通过 DFS 后序遍历累加子树和就能还原每个节点的真实值。这个思路跟一维差分的本质相同都是把“连续区域上的整体操作”转化为“边界点的增量记录”再通过一次累加还原。理解了这一点你遇到新的数据结构或求解场景时就会主动去问这个场景有没有“差分”的等价形式关于差分数组我最想强调的一点是它不只是几行代码更是一种思维模式。当你遇到“区间”“批量化”“离线处理”“边界修改”这些关键词时应该本能地想到差分。如果还想在它基础上再进一步建议动手把二维差分和树上差分各写一遍模板写熟之后你再看区间相关的问题会有一种“一眼看穿”的感觉。这也是我为什么愿意把这篇文章定位成“补充”——它真正重要的不是那几个公式而是怎么把差分思维内化成自己的解题直觉。