“差分数组”这四个字我第一次看到的时候脑子里蹦出的画面是派大星盯着加减法作业发呆的样子被减数、减数、差每个词都认识放到一起却不知道在干什么。后来真把这几个字用在一道区间修改题里我才发现它可能是算法题里性价比最高的技巧之一——原理简单、代码短、跑得又快还透着一种“记账到最后一起结算”的聪明劲。差分数组说穿了就是把原数组变成相邻两项的差再通过一次前缀和把真相还原出来。听起来很平凡但它能优雅地解决一类高频问题区间批量加值、批量减值最后统一查结果。这类题在刷题网站里反复出现今天我就把差分数组的原理、代码、边界处理、常见题型和踩坑经历一次讲清楚。适合刚学完前缀和、正被区间修改折腾的人也适合面试前想快速捡起这个技巧的人。1. 别被名字吓到差分数组就是“记录变化量”1.1 从一道算术题开始被减数、减数、差小时候我们都背过“被减数 - 减数 差”。差分数组干的事本质上就是把这个减法铺到数组相邻元素上。假设有一组数 a [3, 5, 8, 6]从第二个元素开始减前一个d[0] a[0] 3d[1] a[1] - a[0] 5 - 3 2d[2] a[2] - a[1] 8 - 5 3d[3] a[3] - a[2] 6 - 8 -2于是差分数组 d [3, 2, 3, -2]。这里的关键认知是第一个位置没有前一项就把它自己作为起点值。后面的每一项记录的不是“我有多大”而是“我比前一个大了多少、小了多少”。这就像量身高的时候你不记每个人的绝对身高只记“这个人比前一个高几厘米”拿到第一个人的身高和这串差值照样能推出所有人的身高。反过来从 d 恢复 a 就是累加a[1] 3 2 5a[2] 5 3 8a[3] 8 (-2) 6。这种从左往右逐个累加的操作就叫前缀和。如果定义严谨一点设原数组为 a[1..n]差分数组 d[1..n] 满足 d[1] a[1]d[i] a[i] - a[i - 1]i ≥ 2那么恒有 a[i] sum_{j1}^i d[j]。一句话总结差分是前缀和的逆运算。前缀和用来快速求区间和差分用来快速做区间修改两者天然配对。1.2 还原过程一个前缀和就够了构造差分和从差分恢复原数组的代码都极其简单这里用 Python 写一版def build_diff(a): n len(a) d [0] * n d[0] a[0] for i in range(1, n): d[i] a[i] - a[i - 1] return d def restore(d): n len(d) a [0] * n cur 0 for i in range(n): cur d[i] a[i] cur return a a [3, 5, 8, 6] d build_diff(a) # [3, 2, 3, -2] print(restore(d)) # [3, 5, 8, 6]注意 restore 里那个 cur 变量它像个接力棒每经过一个位置就把当前变化量累加起来。要是直接把 d[i] 赋给 a[i]那就丢掉历史累计了得到的结果全是一堆差值不是原数组。这一点我在刚学的时候栽过跟头后面章节会专门讲。到这里差分数组的定义你已经完全掌握了。单看这一步没什么大不了真正精彩的是用它处理“区间修改”也就是下面要说的多米诺骨牌效应。2. 多米诺骨牌连环倒为什么一次操作能影响一整个区间2.1 区间修改的黄金三行代码先看一个高频场景数组 a 可能很长比如 10 万个数要反复执行 m 次“把区间 [l, r] 内每个元素加 x”最后输出最终数组。最直白的暴力写法是for i in range(l, r 1): a[i] x一次区间修改 O(r - l)m 次下来最坏 O(n*m)规模稍大就直接超时。差分数组把单次区间修改降成 O(1)d[l] x if r 1 n: d[r 1] - x对就两行。所有区间操作做完后再跑一遍前缀和还原总复杂度 O(n m)。用一个例子走一遍。假设原数组全 0长度 6即 [0, 0, 0, 0, 0, 0]差分数组一开始也全是 0。现在执行“把下标 1 到 3 全加 5”d[1] 5d 变成 [0, 5, 0, 0, 0, 0]d[4] - 5d 变成 [0, 5, 0, 0, -5, 0]然后跑前缀和还原位置 0cur 0a[0] 0位置 1cur 5a[1] 5位置 2cur 5a[2] 5位置 3cur 5a[3] 5位置 4cur 0a[4] 0位置 5cur 0a[5] 0最终 [0, 5, 5, 5, 0, 0]和预期完全一致。整个过程就像推倒一排多米诺骨牌d[l] x 是第一张被推倒的骨牌前缀和的累加让这股力量一路往右传传到 r1 位置时d[r1] 里那个 -x 像一堵墙把力量拦了下来后面的位置自然不受影响。2.2 为什么偏偏是 r1不是 r这是新手最容易卡住的细节。同样是上面例子如果把减号写在 d[r] 而不是 d[r 1]也就是 d[3] - 5再跑前缀和试试位置 0 是 0位置 1 是 5位置 2 是 5位置 3 变成 0——目标区间的最后一个位置被“误伤”了。因为前缀和累加到 r 时减操作的抵消已经发生连位置 r 自己的加成都没保住。所以闭区间 [l, r] 的“挡板”必须放在 r1 处让位置 r 先享受完完整的加值再在下一格开始抵消。理解了这个原理就不需要死记硬背了。我的经验是第一次接触时在纸上画一条数轴把 l、r、r1 标出来手动走上几遍前缀和比瞪眼背公式管用得多。如果数组是 0-indexed 且 r 恰好是 n-1r1 就越界了。处理方式有两种代码里加个 if 判断或者更省心的做法是直接把数组长度开成 n2下标从 1 开始使用这样 r1 永远有地方放。后面所有例题我都会采用后一种风格。2.3 多张骨牌同时倒差分操作的叠加性实际操作中往往有多次区间修改比如先给 [1, 3] 加 5再给 [2, 4] 加 3。能不能不恢复、直接继续在差分数组上加加减减答案是完全没问题因为差分数组记录的是“变化量”变化量之间天然可以叠加。还用刚才长度为 6 的数组演示第一次修改 [1, 3] 加 5 后d [0, 5, 0, 0, -5, 0]。 第二次修改 [2, 4] 加 3d[2] 3d[5] - 3最终 d [0, 5, 3, 0, -5, -3]。跑一遍前缀和0, 5, 8, 8, 3, 0。验证一下暴力操作先 [1,3] 加 5 得到 [0,5,5,5,0,0]再 [2,4] 加 3 得到 [0,5,8,8,3,0]。一模一样。这种“先记账、后结算”的思路非常像派大星攒了一堆小纸片每准备一次操作就在纸片上记一笔等所有操作都确认了再去换最终答案。因为中间不用反复恢复整个数组效率一下就上来了。3. 三道实战题帮你把差分数组用熟3.1 航班预订统计闭区间加法的标准姿势先看一个最经典的闭区间场景。假设某公司有 n 个航班编号 1 到 n。收到一批预订记录每条记录给三个整数 first、last、seats表示第 first 到第 last 个航班每个航班都增加了 seats 个预订。最后要返回长度 n 的数组第 i 个元素是第 i1 个航班的总预订数。这题就是多次闭区间加法。典型输入如下n 5 bookings [[1, 2, 10], [2, 3, 20], [2, 5, 25]]期望输出是 [10, 55, 45, 25, 25]。用差分解法代码非常短def corp_flight_bookings(bookings, n): diff [0] * (n 2) # 下标 1..n1 都能用多开一位防越界 for first, last, seats in bookings: diff[first] seats diff[last 1] - seats ans [0] * n cur 0 for i in range(1, n 1): cur diff[i] ans[i - 1] cur return ans手动推一下上面例子的 diff记录 [1, 2, 10]diff[1] 10diff[3] - 10记录 [2, 3, 20]diff[2] 20diff[4] - 20记录 [2, 5, 25]diff[2] 25diff[6] - 25最后的 diff 在第 1 到第 6 位分别是10, 45, -10, -20, 0, -25。跑前缀和位置 110位置 255位置 345位置 425位置 525结果 [10, 55, 45, 25, 25] 正好吻合。这种题最容易被卡的地方就是你忘了 last 1 那个减号。我的建议是写代码之前先明确“我现在处理的是闭区间还是左闭右开”再决定减在哪一格。闭区间航班题减在 last1半开区间拼车题减在 end下面马上看到。3.2 拼车与会议室预约左闭右开的站点事件再看一个“区间模板”但边界截然不同的题。假设一辆车有 capacity 个空座收到若干拼车订单每个订单给三个数乘客数 num、上车点 start、下车点 end。请问这辆车能否在整条路线上不超载。这里要抓住一个细节乘客在 start 站上车在 end 站下车。也就是说从 start 出发到 end 之前这一段路车上多了 num 人到达 end 站时人已经下车了。用区间表示就是左闭右开 [start, end)。对应到差分的写法def car_pooling(trips, capacity): diff [0] * 1001 # 假设站点编号不超过 1000 for num, start, end in trips: diff[start] num diff[end] - num # 注意不是 end1 cur 0 for i in range(1001): cur diff[i] if cur capacity: return False return True用例子验证trips [[2, 1, 5], [3, 3, 7]]capacity 4。diff[1] 2diff[5] - 2diff[3] 3diff[7] - 3。扫描到站点 1 时车上 2 人站点 2 还是 2 人站点 3 变成 5 人超载返回 False。如果把 capacity 换成 5就正好通过。会议室预约也是一个套路有一批会议每个会议占用 [start, end) 的时间问同时最多需要多少间会议室。把每次会议看成“进入 1、离开 -1”扫描时间轴统计最大值。代码和拼车几乎一样只是把 num 换成了 1。这两个例子放在一起就能总结出一张对照表场景区间形式加值位置减值位置航班预订[first, last] 闭区间diff[first] seatsdiff[last 1] - seats拼车/上下客[start, end) 左闭右开diff[start] numdiff[end] - num会议室预约[start, end) 左闭右开diff[start] 1diff[end] - 1口诀就一句话看清题目里“结束位置还占不占”占就是闭区间减 end1不占就是半开区间减 end。刷题这么多年边界错一次就得 debug 半天这口诀帮我避了无数坑。3.3 最大重叠区间数扫描线思想的近亲第三类常见题长这样给一堆区间 [start, end]问某个点最多同时被多少个区间覆盖。这类题经常被包装成“某时刻最多有几件事同时发生”“最多重叠区间”等。如果用差分几乎就是模板def max_overlap(intervals): max_end max(end for _, end in intervals) diff [0] * (max_end 2) for start, end in intervals: diff[start] 1 diff[end] - 1 # 具体看题目是闭区间还是开区间 cur 0 ans 0 for i in range(max_end 1): cur diff[i] ans max(ans, cur) return ans比如 intervals [[1, 5], [2, 3], [4, 6], [5, 7]]按 [start, end) 处理位置 5 上第一个区间刚结束-1第四个区间刚开始1抵消后重叠数还是 2最终答案是 2。这种做法的思想叫“扫描线”把所有变化看成事件在时间轴上从左往右扫。差分数组相当于扫描线的朴素实现不用排序、不用堆一个数组加一次循环就解决。见过一些题解用线段树去做这题正确但杀鸡用牛刀。在坐标范围可枚举的场景下差分数组就是最廉价的解法。4. 踩坑记我见过的新手错误全在这4.1 越界判断数组多开一位省一晚上 debug差分的更新操作涉及 l 和 r1或 end如果数组长度刚好是 n更新到边界时极易越界。最常见的错误写法是这样# 错误示范 n 6 diff [0] * n # 下标只能到 5 diff[3] 5 diff[4] - 5 # 万一 r4r15 没问题 # 万一 r5r16 直接 IndexError解决办法通常有两种。第一种把下标整体改成 1-based数组长度设成 n2更新和前缀和都从 1 开始。这是我在所有例题里采用的方式好处是 diff[last 1] 和 diff[end] 不需要任何 if 判断边界问题一次性杜绝。代价是多开一两个空位在算法题里这是完全可接受的。第二种保留 0-based更新时加一个条件。d[l] x if r 1 n: d[r 1] - x也行但每次写区间更新都要记得判断代码多了容易漏。我个人强烈推荐第一种宁愿多开一个格子也不要让边界条件来偷袭你。4.2 别把差分数组当结果数组查有读者问过为什么我做了区间修改输出 d 之后数字还挺大的但和我想要的结果对不上答案很简单d 是“修改的记账本”不是“真实的数组”。真实数组必须经过一次前缀和还原才能得到。比如前面航班预订的例子diff [10, 45, -10, -20, 0, -25]直接看它你根本看不出第 3 个航班有 45 个预订。必须前缀和后才能得到真实答案。如果题目要求在多次修改的过程中随时查询某个位置的值差分数组就不太合适了。因为每次查询都得从开头重新累加最坏 O(n)。这时候该用树状数组或线段树它们支持在线的区间修改和单点查询复杂度 O(log n)。差分数组最适合的场景是所有修改都做完最后统一查结果也就是离线批处理。4.3 负数不可怕溢出才致命差分过程中出现负数是非常正常的事。比如给区间减 1d[l] - 1区间覆盖结束时d[end] - 1。这些负数不是错误结果它们会在前缀和累加时和其他值抵消最终得到正确答案。看到 diff 里有负数别慌先检查自己的逻辑而不是怀疑算法错了。真正容易翻车的是溢出。如果原数组值很大操作次数很多前缀和累加时可能超出 int 范围。C 的 int 上限大约 21 亿别以为不会碰到我曾经在某个大规模模拟题里没把数据类型换成 long long测试数据刚好卡在边界白白调了一个小时。Python 的 int 无溢出问题用 C 做题的同学一定要养成“涉及累加就开 long long”的习惯。4.4 什么时候该用差分什么时候换树状数组刷题多了以后你会发现不是所有“区间修改 查询”都能用差分。整理一个快速决策表需求推荐工具复杂度多次区间修改最后统一求结果差分数组O(n m)在线区间修改 单点查询树状数组O(log n)在线区间修改 区间查询线段树 / 树状数组O(log n)值域巨大比如 1e9且坐标稀疏离散化 差分 / 哈希表取决于离散化后规模区间加 离线查询最终数组差分数组O(n m)选型逻辑要记住差分数组的绝对优势在于实现简单、常数极小但它是离线的。如果操作和查询交替出现在线查询成了刚需就必须上树状数组或者线段树。5. 进阶图景二维差分和树上差分了解一下不亏5.1 二维差分棋盘上的骨牌一维差分能处理数组区间二维差分可以处理矩阵子区域。假设有一个 n 行 m 列的矩阵要执行若干次“把左上角 (x1, y1) 到右下角 (x2, y2) 的子矩阵每个元素加 v”的操作最后求整个矩阵。二维差分的更新公式是四个点diff[x1][y1] v diff[x2 1][y1] - v diff[x1][y2 1] - v diff[x2 1][y2 1] v恢复阶段做二维前缀和for i in range(1, n 1): for j in range(1, m 1): diff[i][j] diff[i - 1][j] diff[i][j - 1] - diff[i - 1][j - 1]第二个公式看起来吓人实际用容斥理解先加上大矩形 (x1..∞, y1..∞) 的 v减掉两片多算的区域再把重叠被减两次的角落加回来。二维和三维的容斥都是一个套路。二维差分的更新是 O(1)恢复是 O(n*m)对于子矩阵批量操作题效果立竿见影。建议新手先把一维玩熟遇到矩阵题再背模板不必一开始就啃二维。5.2 树上差分路径加法的优雅解法简介树上差分也是一样的思想只不过“从左到右的累加”变成了“从叶子到根的累加”。比如要给树的某条路径 (u, v) 上的所有点权加 x最后问每个点的真实权值就可以在几个关键点上做标记最后 DFS 累加子树标记和。点权版的核心标记长这样diff[u] x diff[v] x diff[lca(u, v)] - x diff[parent(lca(u, v))] - x边权版略有不同这里不展开。理解思路即可树上差分仍然在“记录变化量”只是方向从水平扫描换成了树上的父子累加。把一维差分吃透之后看树上差分不会再觉得遥不可及顶多是多算一个 LCA 而已。6. 写在最后一点个人心得我最早学差分数组时是硬背“d[l] val、d[r 1] - val”的结果题目一变形就懵。后来真正理解了“记录变化量”和“最后统一结算”这两个点所有区间类问题在我眼里都清晰了很多。一个小技巧分享给读到这里的你拿到一道区间修改题先连续问自己四个问题——是不是只有区间加/减的批量操作是不是最后统一查结果坐标范围能不能用数组装下区间是闭还是开四个问题都有答案基本就可以放心用差分数组了。写代码时统一 1-based 下标数组多开两位边界问题直接减半。这个技巧我用了很长时间至今仍然觉得它是算法题里“投入产出比”最高的一招。希望派大星这次没白闯你也一样。
