算法刷题系列（十六）：差分——把区间修改变成边界变化
算法刷题系列（十六）：差分——把区间修改变成边界变化
前缀和把区间查询变成两个边界值的相减。差分可以看作它的逆向操作：把一段区间的统一增减，转成区间起点和终点之后的两个边界变化。
它特别适合“有很多次区间加法，最后统一输出数组”的场景。若每次更新都逐个修改区间元素，最坏需要 O(qn)；差分数组可以把每次更新降到 O(1)，最后再用一次前缀累加还原结果。
一、差分数组的定义
对原数组 a 定义：
1
2
diff[0] = a[0]
diff[i] = a[i] - a[i - 1] (i > 0)
对差分数组做前缀累加，就能还原原数组：
1
a[i] = diff[0] + diff[1] + ... + diff[i]
差分记录相邻位置之间的变化；前缀累加把变化还原成当前值。
二、为什么区间更新只需要改两个位置？
给闭区间 [left, right] 中的元素都加上 delta。只需要：
1
2
diff[left] += delta
diff[right + 1] -= delta
从 left 开始的前缀累加会多出 delta；到了 right + 1，减去这份增量，后续位置就恢复原值。
为了支持 right 恰好是最后一个下标，通常为差分数组多留一个哨兵位置。对长度 n 的数组，更新数组大小设为 n + 1。
三、手动推演
初始数组为：
1
[10, 10, 10, 10, 10]
执行两次更新：
1
2
[1, 3] 加 3
[2, 4] 加 -2
先创建全零的增量差分数组，在边界处记录更新：
1
2
diff[1] += 3, diff[4] -= 3
diff[2] -= 2, diff[5] += 2
累加差分后，增量为：
1
[0, 3, 1, 1, -2]
与初始数组相加，得到：
1
[10, 13, 11, 11, 8]
四、Java 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class DifferenceArray {
public static long[] applyRangeAdds(
int[] initial, int[][] updates) {
if (initial == null || updates == null) {
throw new IllegalArgumentException("arguments must not be null");
}
int n = initial.length;
long[] diff = new long[n + 1];
for (int[] update : updates) {
if (update == null || update.length != 3) {
throw new IllegalArgumentException(
"each update must be [left, right, delta]"
);
}
int left = update[0];
int right = update[1];
long delta = update[2];
if (left < 0 || left > right || right >= n) {
throw new IndexOutOfBoundsException("invalid update range");
}
diff[left] += delta;
diff[right + 1] -= delta;
}
long[] result = new long[n];
long added = 0;
for (int i = 0; i < n; i++) {
added += diff[i];
result[i] = initial[i] + added;
}
return result;
}
}
这里不先把原数组转换成差分，而是维护“更新量”的差分，最后将累计更新量加到初始数组。这样输入数组保持不变，且边界含义直观。
五、Python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def apply_range_adds(
initial: list[int], updates: list[tuple[int, int, int]]
) -> list[int]:
if initial is None or updates is None:
raise ValueError("arguments must not be None")
n = len(initial)
diff = [0] * (n + 1)
for left, right, delta in updates:
if left < 0 or left > right or right >= n:
raise IndexError("invalid update range")
diff[left] += delta
diff[right + 1] -= delta
result = []
added = 0
for index, value in enumerate(initial):
added += diff[index]
result.append(value + added)
return result
assert apply_range_adds(
[10, 10, 10, 10, 10],
[(1, 3, 3), (2, 4, -2)],
) == [10, 13, 11, 11, 8]
assert apply_range_adds([], []) == []
Python 类型标注中的区间是闭区间 [left, right]，与前一篇前缀和示例采用的半开区间不同。实际项目中可以统一风格，但应在接口和文档里明确说明。
六、复杂度与使用边界
有 q 次区间更新、数组长度为 n 时：
- 记录每次更新：
O(q)； - 还原结果：
O(n)； - 总时间：
O(n + q)； - 额外空间：
O(n)。
差分数组适合批量更新、最后统一查询的工作负载。若更新后还要立即查询任意区间，简单差分结构不能高效回答；应考虑树状数组、线段树等支持动态操作的数据结构。
七、常见错误
- 忘记在
right + 1撤销增量：会让区间右侧也被修改。 - 未给末尾哨兵留空间：右端点为
n - 1时需要写到diff[n]。 - 把闭区间与半开区间混淆：本例更新
[left, right]，撤销位置是right + 1。 - 累加恢复时从错误位置开始：结果位置
i使用的是diff[0..i]的累计值。 - 每次更新直接遍历整个区间：这失去了差分将更新压缩到边界的优势。
- 误用在需要实时查询的场景：差分擅长批处理，不是所有动态数组问题的答案。
八、与下一篇的连接
差分把许多区间更新压缩成边界变化；滑动窗口则维护一个当前连续区间，随着左右端点移动不断加入或移除元素。下一篇将讨论何时窗口可以单调收缩，以及为什么这个方法通常要求非负数等单调条件。
小结
闭区间加法只改变差分数组的 left 和 right + 1 两个边界。将所有更新记录完，再对差分做一次前缀累加即可恢复总效果。要记牢区间端点约定、末尾哨兵和批处理适用场景。