差分数组（Difference Array）及其应用

差分数组是一种处理区间更新操作的高效数据结构。它允许我们在 O(1) 时间内对一个原始数组的任意区间进行统一增减操作，然后可以在 O(n) 时间内通过差分数组重建出更新后的原始数组。这在频繁进行区间修改、单点查询或最终统一查询的场景下非常高效。

1. 差分数组的基本思想

假设我们有一个长度为 n 的原始数组 arr（索引从 0 到 n-1）。
我们定义另一个同样长度为 n 的数组 diff 作为 arr 的差分数组，其中：

• diff[0] = arr[0]
• 对于 i >= 1，diff[i] = arr[i] - arr[i-1]

关键性质：

• 从差分数组 diff 恢复原始数组 arr：arr[i] = diff[0] + diff[1] + ... + diff[i]。即 arr[i] 是 diff 从 0 到 i 的前缀和。
• 如果我们想对原始数组 arr 的区间 [L, R]（闭区间）内所有元素统一加上一个值 val，只需要在差分数组上做两个操作：
  1. diff[L] += val
  2. 如果 R + 1 < n，则 diff[R + 1] -= val
     这样，后续通过前缀和恢复 arr 时，从索引 L 开始，所有元素都会自动加上 val，而在 R+1 处又减回去，从而保证只有区间 [L, R] 受到影响。

2. 详细步骤与示例

步骤1：构建初始差分数组

给定原始数组 arr = [1, 3, 5, 2, 4]，长度为 5。
构建差分数组 diff：

• diff[0] = arr[0] = 1
• diff[1] = arr[1] - arr[0] = 3 - 1 = 2
• diff[2] = arr[2] - arr[1] = 5 - 3 = 2
• diff[3] = arr[3] - arr[2] = 2 - 5 = -3
• diff[4] = arr[4] - arr[3] = 4 - 2 = 2
  所以 diff = [1, 2, 2, -3, 2]。

验证恢复：arr[2] = diff[0] + diff[1] + diff[2] = 1 + 2 + 2 = 5，正确。

步骤2：进行区间更新

假设我们要对 arr 的区间 [1, 3] 内每个元素加 5。
在差分数组 diff 上操作：

• diff[1] += 5 → diff[1] 从 2 变为 7
• 因为 R+1 = 4 在数组范围内，所以 diff[4] -= 5 → diff[4] 从 2 变为 -3
  更新后 diff = [1, 7, 2, -3, -3]。

步骤3：通过差分数组恢复更新后的原始数组

计算前缀和：

• newArr[0] = diff[0] = 1
• newArr[1] = diff[0] + diff[1] = 1 + 7 = 8
• newArr[2] = 1 + 7 + 2 = 10
• newArr[3] = 1 + 7 + 2 + (-3) = 7
• newArr[4] = 1 + 7 + 2 + (-3) + (-3) = 4
  得到 newArr = [1, 8, 10, 7, 4]。

验证：原始 arr 为 [1, 3, 5, 2, 4]，区间 [1,3] 加 5 后应为 [1, 8, 10, 7, 4]，完全一致。

3. 代码实现模板（Python）

class DifferenceArray:
    def __init__(self, nums):
        self.n = len(nums)
        self.diff = [0] * self.n
        # 构建初始差分数组
        self.diff[0] = nums[0]
        for i in range(1, self.n):
            self.diff[i] = nums[i] - nums[i-1]
    
    def range_add(self, left, right, val):
        """对区间 [left, right] 内所有元素加 val"""
        self.diff[left] += val
        if right + 1 < self.n:
            self.diff[right + 1] -= val
    
    def recover(self):
        """从差分数组恢复原始数组（即更新后的数组）"""
        res = [0] * self.n
        res[0] = self.diff[0]
        for i in range(1, self.n):
            res[i] = res[i-1] + self.diff[i]
        return res

# 使用示例
nums = [1, 3, 5, 2, 4]
da = DifferenceArray(nums)
da.range_add(1, 3, 5)
print(da.recover())  # 输出: [1, 8, 10, 7, 4]

4. 典型应用场景

1. 区间增减，单点查询：在多次区间更新后，查询某个位置的当前值。只需在差分数组上更新，查询时计算前缀和即可。
2. 航班预订统计：有 n 个航班， bookings[i] = [first, last, seats] 表示对航班编号从 first 到 last 的每个航班预订 seats 个座位。返回所有航班预订座位数。这正是对区间 [first-1, last-1] 统一加 seats，使用差分数组可在 O(m + n) 时间内解决（m 为 bookings 数量）。
3. 拼车问题：行程 trips[i] = [numPassengers, start, end] 表示有乘客在 start 上车，end 下车。判断车辆容量是否足够。可将每个行程视为在时间区间 [start, end) 内增加乘客数，用差分数组统计每个时间点的乘客数。
4. 会议室安排 II：给定一系列会议的开始和结束时间，计算同时进行会议的最大数量。可将每个会议视为在 [start, end) 区间内占用一个会议室，用差分数组统计每个时间点的会议数量。

5. 复杂度分析

• 构建差分数组：O(n)
• 区间更新：O(1)
• 恢复数组：O(n)
  若进行 m 次区间更新，最后查询整个数组，总复杂度为 O(n + m)，比直接对原数组每次更新区间 O(m * k)（k为区间平均长度）高效得多。

差分数组的核心优势在于将区间更新的时间复杂度从 O(k) 降为 O(1)，通过后续的前缀和“延迟”计算，在需要时才付出 O(n) 的代价。