02_差分数组

差分数组

模板

diff = [0] * (n + 1)   # 开 n+1，防止 r+1 越界

# 对区间 [l, r] 加 v
diff[l] += v
diff[r+1] -= v

# 还原：对 diff 求前缀和
arr = [0] * n
curr = 0
for i in range(n):
    curr += diff[i]
    arr[i] = curr

字典版（稀疏差分）

当下标很大或很稀疏（只涉及少数几个位置）时，用字典代替数组：

diff = {}

# 对区间 [l, r) 加 v
diff[l] = diff.get(l, 0) + v    # 起点加 v
diff[r] = diff.get(r, 0) - v    # 终点减 v

解释

用途：多次区间修改、最后一次性还原——每次把「区间 $[l, r]$ 整体加 $v$」降为 $O(1)$ 的两个单点修改。

原理：差分是前缀和的逆运算。设 $d[i] = a[i] - a[i-1]$，则对 $d$ 求前缀和就还原出 $a$。区间 $[l, r]$ 加 $v$ 时，只有 $d[l]$ 和 $d[r+1]$ 两个边界变了：

$$d[l] \mathrel{+}= v,\quad d[r+1] \mathrel{-}= v$$

典型例题：LeetCode 1109. 航班预订统计

有 n 个航班，bookings[i] = [first, last, seats] 表示预订区间 [first, last] 的每个航班增加 seats 个座位，求各航班最终预订数。典型的「多次区间修改 + 最后还原」：

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        diff = [0] * (n + 1)
        for first, last, seats in bookings:  # 题目是 1-indexed
            diff[first - 1] += seats
            diff[last] -= seats

        ans = []
        curr = 0
        for i in range(n):
            curr += diff[i]
            ans.append(curr)
        return ans

适用场景与限制

• 适合：所有修改先做完、最后统一查询/还原（离线场景），总复杂度 $O(n + m)$
• 不适合：修改和查询交替进行（在线场景）——每次查询都要 $O(n)$ 还原，应改用树状数组或线段树
• 常见变形：对「区间被覆盖次数」计数（如拼车、会议室占用），同样先差分再前缀和