差分数组与前缀和

2026-06-02

差分数组 = 前缀和的逆运算。区间 [l, r] += k 这种 的活，改成两次单点改 diff[l] += k; diff[r+1] -= k, 搞定。最后再做一遍前缀和还原。记住这一句,这辈子的区间批量加都不会再写循环。

直觉 — 前缀和的逆运算

把”求和”和”差分”想成函数:

操作 公式 类比
前缀和 pre[i] = pre[i-1] + a[i] 积分 ∫
差分 diff[i] = a[i] - a[i-1] 求导 d/dx

两个互为逆运算: 先差分再前缀和 = 原数组。这不是巧合,就是离散版本的微积分基本定理。

所以一个想法立刻浮现: 既然修改”原数组的一段区间”很贵( 个点都要碰),那就去修改”差分数组”,代价只在两个端点。最后做一次前缀和就把所有修改批量”实例化”出来。

为什么是两个端点

设原数组 ,差分 。区间 后,新的差分:

  • 变了: 加了 , 没变,所以 。
  • 变了: 没变, 加了 ,所以 。
  • 中间 的 : 前后都加了 ,差不变。

整段区间的修改,只在两个端点留下痕迹。这就是差分省时间的根。

动画 — 跟着端点走

下面的动画用长度 8 的数组演示三次区间加: [1,4]+3、[2,6]+2、[5,7]+1。每点一次”下一步”,看一对端点(绿色 +、红色 -)在 diff 上落子;六次落子完成后,做一次前缀和还原出最终结果数组。

重点观察: 修改阶段从来不碰中间,只在 l 和 r+1 两个位置变化;还原阶段一次扫描搞定。

模板 — Python

1
2
3
4
5
6
7
8
9
10
11
12
def range_add(n, ops):
    """ops: List[(l, r, k)], 对长度 n 的全 0 数组执行多次 [l, r] += k"""
    diff = [0] * (n + 1)            # 多开 1 位,避免 r+1 越界判断
    for l, r, k in ops:
        diff[l] += k
        diff[r + 1] -= k            # 关键: 是 r+1,不是 r
    # 前缀和还原
    a = [0] * n
    a[0] = diff[0]
    for i in range(1, n):
        a[i] = a[i - 1] + diff[i]
    return a

三个易错点:

  1. diff 开 n+1 长度,省掉 if r+1 < n 的判断。
  2. 闭区间 [l, r] 对应 diff[r+1] -= k;如果题目给的是半开区间 [l, r),那就是 diff[r] -= k。
  3. 如果原数组不是全 0,先对原数组做一遍差分得到初始 diff,再叠加操作。

与前缀和的对偶

1
2
3
4
5
6
7
# 前缀和: 查询区间和 O(1),数组不变
pre[i] = pre[i-1] + a[i]
sum(a[l..r]) = pre[r+1] - pre[l]

# 差分: 区间修改 O(1),查询要还原
diff[l] += k; diff[r+1] -= k
a[i] = diff[0] + diff[1] + ... + diff[i]

一个是”只查不改”,一个是”只改不查”。两者对偶,选哪个看题目要的是查询多还是修改多。 修改和查询交替进行的场景,才上线段树。

二维差分 — 矩形批量加

把一维的两端点扩展到矩形的四个角。对子矩形 加 :

1
2
3
4
diff[r1][c1]     += k
diff[r1][c2+1]   -= k
diff[r2+1][c1]   -= k
diff[r2+1][c2+1] += k   # 容斥,把多减的补回来

还原用二维前缀和: a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + diff[i][j]。模板题: LC 2536. 子矩阵元素加 1。

记忆口诀: 左上 +, 右下外两侧 -, 右下外的对角 +。和二维前缀和的容斥公式严格对偶。

经典题 — 1109. 航班预订统计

n 个航班,给定 bookings[i] = [first, last, seats] 表示从第 first 到 last 班(闭区间)每班预订 seats 个座位。返回每班的总座位数。

直接套模板,注意题目下标从 1 开始:

1
2
3
4
5
6
7
8
9
class Solution:
    def corpFlightBookings(self, bookings, n):
        diff = [0] * (n + 1)
        for f, l, s in bookings:
            diff[f - 1] += s        # 转 0-indexed
            diff[l] -= s            # l-1 是右端点,所以 r+1 = l
        for i in range(1, n):
            diff[i] += diff[i - 1]
        return diff[:n]

复杂度 , 是预订次数。暴力法是 ,数据量稍大就 TLE。

其他必刷:

记忆法

一句话: 改区间,改两端;还原靠前缀和。

三个对仗:

维度 前缀和 差分
解决问题 区间查询 区间修改
操作 累加 取差
微积分类比 积分 求导

判题口诀:

  • 只查不改 → 前缀和
  • 只改后查(可以离线) → 差分
  • 改查交替(必须在线) → 线段树

看到”对一段区间统一加/减”再加”最后一次性输出/查询”,条件反射写 diff[l] += k; diff[r+1] -= k。错不了。