差分数组（Difference Array）原理与应用

差分数组是一种用于高效处理数组区间更新操作的数据结构。其核心思想是将对原数组某个区间内所有元素的增减操作，转化为对差分数组两个端点的修改，从而将区间更新操作的时间复杂度从 O(n) 优化为 O(1)。

一、 问题引入与基本思想

问题场景： 给定一个初始全为0的长度为 n 的数组 arr，我们需要处理 m 个操作。每个操作指定一个区间 [L, R] 和一个值 val，表示将 arr[L] 到 arr[R] 之间的每个元素都加上 val。所有操作完成后，需要得到最终的 arr 数组。

直观方法：
每次操作遍历区间 [L, R]，对每个位置进行加法，时间复杂度为 O(R-L+1)。m 次操作后，最坏时间复杂度为 O(m*n)，当 n 和 m 都很大时（例如 10^5 级别），效率极低。

差分思想：

1. 我们引入一个长度也为 n 的“差分数组” diff。diff[0] = arr[0]，对于 i ≥ 1，diff[i] = arr[i] - arr[i-1]。即 diff[i] 记录的是原数组相邻元素的差值。
2. 关键性质：原数组是差分数组的前缀和。也就是说，arr[i] = diff[0] + diff[1] + ... + diff[i]。
3. 更关键的是：如果我们想对原数组的区间 [L, R] 统一加上 val，我们不需要遍历整个区间。只需要修改差分数组的两个点：
   • diff[L] += val。这意味着从位置 L 开始，原数组的每个元素都比前一个元素（相对于其差分关系）多 val，所以从 L 往后的所有元素都会间接加上 val。
   • diff[R+1] -= val (当 R+1 < n 时)。这表示在区间结束后（R+1 位置），我们要把这个“多出来的差值”给抵消掉，这样 R+1 之后的元素就不会受到这次区间加法的持续影响了。

二、 差分数组的构建与操作步骤详解

假设我们有一个初始数组 arr（长度 n）。

步骤1：构建差分数组 diff

diff[0] = arr[0]
for i from 1 to n-1:
    diff[i] = arr[i] - arr[i-1]

如果 arr 初始全为0，则 diff 也全为0。通常我们从全0数组开始处理区间更新，所以初始 diff 就是一个全0数组，这简化了过程。

步骤2：执行区间更新操作
对于每个操作 (L, R, val)：

diff[L] += val
if R + 1 < n:
    diff[R+1] -= val

无论区间 [L, R] 有多长，我们都只进行了两次 O(1) 的运算。

步骤3：从差分数组恢复最终的原数组
对差分数组 diff 计算前缀和，结果就是更新后的 arr。

arr[0] = diff[0]
for i from 1 to n-1:
    arr[i] = arr[i-1] + diff[i]

这个过程的时间复杂度是 O(n)。

举例说明：
初始数组 arr = [0, 0, 0, 0, 0] (n=5)。因此初始差分数组 diff = [0, 0, 0, 0, 0]。

操作1：对区间 [1, 3] 加 5。

• diff[1] += 5 -> diff = [0, 5, 0, 0, 0]
• R+1=4 < 5，所以 diff[4] -= 5 -> diff = [0, 5, 0, 0, -5]

操作2：对区间 [2, 4] 加 2。

• diff[2] += 2 -> diff = [0, 5, 2, 0, -5]
• R+1=5 不小于 n=5，所以不做操作。

现在，我们通过前缀和恢复 arr：

• arr[0] = diff[0] = 0
• arr[1] = arr[0] + diff[1] = 0 + 5 = 5
• arr[2] = arr[1] + diff[2] = 5 + 2 = 7
• arr[3] = arr[2] + diff[3] = 7 + 0 = 7
• arr[4] = arr[3] + diff[4] = 7 + (-5) = 2

最终 arr = [0, 5, 7, 7, 2]，符合预期：位置1是5，位置2和3是5+2=7，位置4是2。

三、 算法复杂度与优势

• 构建差分数组：O(n)，如果从全0开始则 O(1)。
• 单次区间更新：O(1)。
• 恢复原数组：O(n)。

优势：在处理大量区间加减更新、少量（或最后）查询的场景下，差分数组将总时间复杂度从暴力法的 O(m*n) 降低到 O(m + n)，效率提升巨大。

四、 典型应用场景

1. 航班预订统计：有 n 个航班， bookings[i] = [first_i, last_i, seats_i] 表示在区间 [first_i, last_i] 的每个航班上预定了 seats_i 个座位。求每个航班的总预定数。这正是差分数组的模板题。
2. 区间增减后查询：大量“区间内所有元素加/减一个值”的操作后，询问某个位置的值，或者询问所有位置的最终值。
3. 前缀和的“逆运算”：当问题可以转化为对原数组的区间操作时，差分是前缀和思想的一种逆向应用。前缀和常用于快速求区间和，而差分常用于快速进行区间修改。
4. 二维差分：概念可以扩展到二维矩阵。在二维矩阵中，如果想对以 (x1, y1) 为左上角，(x2, y2) 为右下角的子矩阵统一加 val，只需要在二维差分矩阵的四个角做 O(1) 修改：
   • diff[x1][y1] += val
   • diff[x1][y2+1] -= val (如果 y2+1 不越界)
   • diff[x2+1][y1] -= val (如果 x2+1 不越界)
   • diff[x2+1][y2+1] += val (如果 x2+1 和 y2+1 都不越界)
     最后对二维差分矩阵求二维前缀和即可得到更新后的原矩阵。

五、 总结

差分数组的核心在于将作用在区间上的累积变化量，用边界上的“差分”变化来表示。它牺牲了单点查询的即时性（需要计算前缀和才能得到当前值），但换来了区间更新操作的极致效率。在解决特定的批量区间更新问题时，它是一个非常简洁而强大的工具。理解差分数组，关键在于掌握其定义、区间更新时两个端点的修改逻辑，以及它与原数组（前缀和）的互逆关系。