企业官网建设流程全解析

“差分数组”这四个字我第一次看到的时候，脑子里蹦出的画面是派大星盯着加减法作业发呆的样子：被减数、减数、差，每个词都认识，放到一起却不知道在干什么。后来真把这几个字用在一道区间修改题里，我才发现它可能是算法题里性价比最高的技巧之一——原理简单、代码短、跑得又快，还透着一种“记账到最后一起结算”的聪明劲。

差分数组说穿了，就是把原数组变成相邻两项的差，再通过一次前缀和把真相还原出来。听起来很平凡，但它能优雅地解决一类高频问题：区间批量加值、批量减值，最后统一查结果。这类题在刷题网站里反复出现，今天我就把差分数组的原理、代码、边界处理、常见题型和踩坑经历一次讲清楚。适合刚学完前缀和、正被区间修改折腾的人，也适合面试前想快速捡起这个技巧的人。

1. 别被名字吓到：差分数组就是“记录变化量”

1.1 从一道算术题开始：被减数、减数、差

小时候我们都背过“被减数 - 减数 = 差”。差分数组干的事，本质上就是把这个减法铺到数组相邻元素上。

假设有一组数 a = [3, 5, 8, 6]，从第二个元素开始减前一个：

• d[0] = a[0] = 3
• d[1] = a[1] - a[0] = 5 - 3 = 2
• d[2] = a[2] - a[1] = 8 - 5 = 3
• d[3] = a[3] - a[2] = 6 - 8 = -2

于是差分数组 d = [3, 2, 3, -2]。

这里的关键认知是：第一个位置没有前一项，就把它自己作为起点值。后面的每一项，记录的不是“我有多大”，而是“我比前一个大了多少、小了多少”。这就像量身高的时候，你不记每个人的绝对身高，只记“这个人比前一个高几厘米”，拿到第一个人的身高和这串差值，照样能推出所有人的身高。

反过来从 d 恢复 a 就是累加：a[1] = 3 + 2 = 5，a[2] = 5 + 3 = 8，a[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_{j=1}^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] += 5，d 变成 [0, 5, 0, 0, 0, 0]
• d[4] -= 5，d 变成 [0, 5, 0, 0, -5, 0]

然后跑前缀和还原：

• 位置 0：cur = 0，a[0] = 0
• 位置 1：cur = 5，a[1] = 5
• 位置 2：cur = 5，a[2] = 5
• 位置 3：cur = 5，a[3] = 5
• 位置 4：cur = 0，a[4] = 0
• 位置 5：cur = 0，a[5] = 0

最终 [0, 5, 5, 5, 0, 0]，和预期完全一致。整个过程就像推倒一排多米诺骨牌：d[l] += x 是第一张被推倒的骨牌，前缀和的累加让这股力量一路往右传；传到 r+1 位置时，d[r+1] 里那个 -x 像一堵墙，把力量拦了下来，后面的位置自然不受影响。

2.2 为什么偏偏是 r+1，不是 r

这是新手最容易卡住的细节。同样是上面例子，如果把减号写在 d[r] 而不是 d[r + 1]，也就是 d[3] -= 5，再跑前缀和试试：位置 0 是 0，位置 1 是 5，位置 2 是 5，位置 3 变成 0——目标区间的最后一个位置被“误伤”了。因为前缀和累加到 r 时，减操作的抵消已经发生，连位置 r 自己的加成都没保住。

所以闭区间 [l, r] 的“挡板”必须放在 r+1 处，让位置 r 先享受完完整的加值，再在下一格开始抵消。理解了这个原理，就不需要死记硬背了。我的经验是：第一次接触时在纸上画一条数轴，把 l、r、r+1 标出来，手动走上几遍前缀和，比瞪眼背公式管用得多。

如果数组是 0-indexed 且 r 恰好是 n-1，r+1 就越界了。处理方式有两种：代码里加个 if 判断，或者更省心的做法是直接把数组长度开成 n+2，下标从 1 开始使用，这样 r+1 永远有地方放。后面所有例题我都会采用后一种风格。

2.3 多张骨牌同时倒：差分操作的叠加性

实际操作中往往有多次区间修改，比如先给 [1, 3] 加 5，再给 [2, 4] 加 3。能不能不恢复、直接继续在差分数组上加加减减？答案是完全没问题，因为差分数组记录的是“变化量”，变化量之间天然可以叠加。

还用刚才长度为 6 的数组演示：

第一次修改 [1, 3] 加 5 后，d = [0, 5, 0, 0, -5, 0]。 第二次修改 [2, 4] 加 3：

• d[2] += 3
• d[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 个元素是第 i+1 个航班的总预订数。

这题就是多次闭区间加法。典型输入如下：

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..n+1 都能用，多开一位防越界 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] += 10，diff[3] -= 10
• 记录 [2, 3, 20]：diff[2] += 20，diff[4] -= 20
• 记录 [2, 5, 25]：diff[2] += 25，diff[6] -= 25

最后的 diff 在第 1 到第 6 位分别是：10, 45, -10, -20, 0, -25。跑前缀和：

• 位置 1：10
• 位置 2：55
• 位置 3：45
• 位置 4：25
• 位置 5：25

结果 [10, 55, 45, 25, 25] 正好吻合。

这种题最容易被卡的地方就是你忘了 last + 1 那个减号。我的建议是：写代码之前先明确“我现在处理的是闭区间还是左闭右开”，再决定减在哪一格。闭区间航班题，减在 last+1；半开区间拼车题，减在 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 # 注意：不是 end+1 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] += 2，diff[5] -= 2；diff[3] += 3，diff[7] -= 3。扫描到站点 1 时车上 2 人，站点 2 还是 2 人，站点 3 变成 5 人，超载，返回 False。如果把 capacity 换成 5，就正好通过。

会议室预约也是一个套路：有一批会议，每个会议占用 [start, end) 的时间，问同时最多需要多少间会议室。把每次会议看成“进入 +1、离开 -1”，扫描时间轴统计最大值。代码和拼车几乎一样，只是把 num 换成了 1。

这两个例子放在一起，就能总结出一张对照表：

口诀就一句话：看清题目里“结束位置还占不占”，占就是闭区间减 end+1，不占就是半开区间减 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 和 r+1（或 end），如果数组长度刚好是 n，更新到边界时极易越界。最常见的错误写法是这样：

# 错误示范 n = 6 diff = [0] * n # 下标只能到 5 diff[3] += 5 diff[4] -= 5 # 万一 r=4，r+1=5 没问题 # 万一 r=5，r+1=6 直接 IndexError

解决办法通常有两种。

第一种：把下标整体改成 1-based，数组长度设成 n+2，更新和前缀和都从 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 负数不可怕，溢出才致命

差分过程中出现负数是非常正常的事。比如给区间减 1，d[l] -= 1；区间覆盖结束时，d[end] -= 1。这些负数不是错误结果，它们会在前缀和累加时和其他值抵消，最终得到正确答案。

看到 diff 里有负数别慌，先检查自己的逻辑，而不是怀疑算法错了。

真正容易翻车的是溢出。如果原数组值很大，操作次数很多，前缀和累加时可能超出 int 范围。C++ 的 int 上限大约 21 亿，别以为不会碰到；我曾经在某个大规模模拟题里没把数据类型换成 long long，测试数据刚好卡在边界，白白调了一个小时。Python 的 int 无溢出问题，用 C++ 做题的同学一定要养成“涉及累加就开 long long”的习惯。

4.4 什么时候该用差分，什么时候换树状数组

刷题多了以后，你会发现不是所有“区间修改 + 查询”都能用差分。整理一个快速决策表：

选型逻辑要记住：差分数组的绝对优势在于实现简单、常数极小，但它是离线的。如果操作和查询交替出现，在线查询成了刚需，就必须上树状数组或者线段树。

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 下标，数组多开两位，边界问题直接减半。

这个技巧我用了很长时间，至今仍然觉得它是算法题里“投入产出比”最高的一招。希望派大星这次没白闯，你也一样。