差分数组法（Difference Array）

差分数组法（Difference Array）是一种用于高效处理数组区间更新操作的技术，特别适合解决“多次对数组某个区间进行增减操作，最后查询结果”的问题。其核心思想是通过差分数组将区间操作转化为单点操作，大幅降低时间复杂度。

核心概念

1. 差分数组定义
   给定原数组 arr，其差分数组 diff 满足：

   • diff[0] = arr[0]
   • diff[i] = arr[i] - arr[i-1]（当 i > 0 时）

   示例：
   原数组 arr = [3, 5, 2, 7]
   差分数组 diff = [3, 2, -3, 5]（计算过程：5-3=2, 2-5=-3, 7-2=5）

2. 核心操作：区间增减
   若要对 arr 的区间 [i, j] 统一增加 k，只需修改差分数组的两个位置：

   • diff[i] += k
   • diff[j+1] -= k（若 j+1 越界则忽略）

3. 还原原数组
   通过差分数组求前缀和即可还原操作后的数组：

   arr[0] = diff[0];
   arr[i] = diff[i] + arr[i-1]; // i ≥ 1

优势分析

• 传统方法：每次区间更新需遍历整个区间，m 次操作时间复杂度为 O(m·n)。
• 差分数组：区间更新转化为两个单点操作，m 次操作时间复杂度为 O(m + n)。

代码实现

class Difference {
  constructor(nums) {
    this.diff = new Array(nums.length);
    this.diff[0] = nums[0];
    for (let i = 1; i < nums.length; i++) {
      this.diff[i] = nums[i] - nums[i - 1];
    }
  }

  // 区间 [i, j] 增加 val（包含 i 和 j）
  increment(i, j, val) {
    this.diff[i] += val;
    if (j + 1 < this.diff.length) {
      this.diff[j + 1] -= val;
    }
  }

  // 返回更新后的数组
  result() {
    const res = new Array(this.diff.length);
    res[0] = this.diff[0];
    for (let i = 1; i < this.diff.length; i++) {
      res[i] = res[i - 1] + this.diff[i];
    }
    return res;
  }
}

使用示例

const arr = [3, 5, 2, 7];
const df = new Difference(arr);

// 对区间 [1, 2] 增加 4（即索引1到2的元素+4）
df.increment(1, 2, 4);

console.log(df.result()); // 输出: [3, 9, 6, 7]
// 解释: 
// 原数组 [3, 5, 2, 7]
// 操作后: 索引1:5+4=9, 索引2:2+4=6 → [3, 9, 6, 7]

应用场景

1. 航班预订统计（LeetCode 1109）
   有 n 个航班，预订记录 bookings = [[i, j, k]] 表示航班 i 到 j 各预订 k 个座位，求每个航班的预订总数。

2. 拼车问题（LeetCode 1094）
   判断车辆能否在途中接载所有乘客（乘客上下车导致容量变化）。

3. 区间加法（LeetCode 370）
   对数组进行多次区间加减操作，返回最终结果。

总结

• 核心价值：将区间操作的复杂度从 O(n) 降为 O(1)。
• 适用条件：离线操作（先完成所有更新，最后查询结果）。
• 关键点：通过差分数组将区间更新转化为端点修改，最后通过前缀和还原结果。

通过掌握差分数组法，可高效解决一系列区间更新问题，显著优化算法性能。