差分数组完全指南 - 掌握 O(1) 时间复杂度的区间更新

概述

差分数组是处理多次区间更新的强大技术，是前缀和的逆运算，在以下场景中至关重要：

区间加减操作
时间轴模拟
预订系统
区间操作问题

为什么面试官喜欢考它：测试你将 O(n×m) 暴力解法优化到 O(n+m) 的能力。

⏱️ 时间复杂度

构建：O(n) — 一次遍历创建差分数组
更新：O(1) — 每次区间更新只需常数时间！
重构：O(n) — 应用前缀和得到最终结果

💾 空间复杂度

O(n) — 存储差分数组

📋 使用场景

多次区间更新，较少查询
预订/预约系统
时间轴事件处理
更新操作远多于查询操作

🔗 与前缀和的关系

差分数组和前缀和是互逆运算！

美妙的对称性

原数组 ←────────→ 差分数组
        差分         前缀和

正向（构建差分数组）：

arr[i] → diff[i] = arr[i] - arr[i-1]

反向（重构数组）：

diff[i] → arr[i] = arr[i-1] + diff[i]  (前缀和！)

可视化对比

数组：      [3,  5,  2,  7,  4]
索引：       0   1   2   3   4

差分：      [3,  2, -3,  5, -3]
            ↑   ↑   ↑   ↑   ↑
           3  5-3 2-5 7-2 4-7

核心洞察 💡

操作	前缀和	差分数组
构建	累加和	计算差值
用途	快速区间查询	快速区间更新
更新	O(n)	O(1) ✓
查询	O(1) ✓	O(n)
重构	不需要	需要前缀和！

关键联系：

前缀和累积变化
差分数组记录变化
它们是数学上的逆运算！

构建差分数组

💡 算法

创建大小为 n + 1 的数组（边界需要额外空间）
设置 diff[0] = arr[0]（基础情况）
对于每个索引 i，计算 diff[i] = arr[i] - arr[i-1]

🎮 交互式可视化

观看差分数组如何捕获相邻元素之间的变化。

Building Difference Array

Step 1 of 7

Initial Array

Start with original array

Original Array:

[0]

[1]

[2]

[3]

[4]

Difference Array:

[0]

[1]

[2]

[3]

[4]

[5]

Click Next to continue

💻 模板代码

✅ 关键点

大小：差分数组有 n + 1 个元素（边界需要额外空间）
首元素：diff[0] = arr[0]（没有前一个元素）
差分：diff[i] 存储从 arr[i-1] 到 arr[i] 的变化
时间：O(n) 构建
目的：记录增量变化

O(1) 区间更新 ⚡

这是差分数组的杀手级特性！

💡 神奇公式

给区间 [left, right] 加上 value：

diff[left] += value;      // 标记区间起点
diff[right + 1] -= value; // 标记区间终点

为什么有效？

当我们使用前缀和重构时：
  
  位置 left:         从 diff[left] 获得 +value
  位置 (left+1) 到 right: 继承 +value（前缀和会传递）
  位置 (right+1):    获得 -value，抵消效果
  后面的位置：        无影响（已抵消）

🎮 交互式可视化

看看区间更新如何只修改两个位置！

Range Update in O(1)

Step 1 of 5

Initial State

Original array and its difference array

Original Array:

[0]

[1]

[2]

[3]

[4]

Difference Array:

-3

[0]

[1]

[2]

[3]

[4]

[5]

Click Next to continue

💻 模板代码

📊 详细示例

初始数组：   [3, 5, 2, 7, 4]
初始差分：   [3, 2, -3, 5, -3, 0]

操作：给区间 [1, 3] 加上 10
────────────────────────────────────

步骤 1：diff[1] += 10
   diff = [3, 12, -3, 5, -3, 0]
         ─────↑

步骤 2：diff[4] -= 10
   diff = [3, 12, -3, 5, -13, 0]
         ─────────────────↑

重构（应用前缀和）：
   [3, 15, 12, 17, 4]
       ↑   ↑   ↑
    这些位置加了 10！ ✓

复杂度分析

方法	每次更新时间	m 次更新总时间
暴力解法	O(n)	O(n × m)
差分数组	O(1) ✓	O(m) ✓

对于 10000 大小的数组进行 1000 次更新：

暴力解法：10,000,000 次操作
差分数组：1,000 次操作 + 重构

快 10,000 倍！ 🚀

重构数组

所有更新完成后，我们需要得到最终数组。这就是前缀和登场的时候！

💡 算法

对差分数组应用前缀和：

arr[0] = diff[0]
arr[i] = arr[i-1] + diff[i]  // 前缀和！

🎮 交互式可视化

观看前缀和如何将差分数组转换回原数组。

Reconstructing Array (Prefix Sum)

Step 1 of 7

After Updates

Difference array after multiple range updates

Original Array:

[0]

[1]

[2]

[3]

[4]

Difference Array:

-3

-13

[0]

[1]

[2]

[3]

[4]

[5]

Click Next to continue

💻 模板代码

完整工作流程

步骤 1：构建差分数组
   数组：  [3, 5, 2, 7, 4]
     ↓
   差分：  [3, 2, -3, 5, -3, 0]

步骤 2：应用更新（每次 O(1)）
   更新 [1,3] +10: diff[1]+=10, diff[4]-=10
   更新 [0,2] -5:  diff[0]-=5, diff[3]+=5
     ↓
   差分：  [-2, 12, -3, 10, -13, 0]

步骤 3：重构（前缀和）
     ↓
   结果：  [-2, 10, 7, 17, 4]

面试题目

问题一：区间加法 (LC 370) 🔒

注意：这是一道 LeetCode 会员题。需要订阅才能提交。

问题：给定一个长度为 n 初始化为 0 的数组，和一系列区间更新操作，返回最终数组。

输入：length = 5, updates = [[1,3,2], [2,4,3], [0,2,-2]]
输出：[-2, 0, 3, 5, 3]

解释：
初始：            [0, 0, 0, 0, 0]
执行 [1,3,2]:    [0, 2, 2, 2, 0]
执行 [2,4,3]:    [0, 2, 5, 5, 3]
执行 [0,2,-2]:   [-2, 0, 3, 5, 3]

关键洞察：差分数组的完美应用场景！

复杂度：O(n + m) 时间，O(n) 空间，其中 m = 更新次数

面试提示：这是基础模式 — 先掌握这个！

问题二：航班预订统计 (LC 1109)

问题：处理航班预订，每个预订在一段航班区间上预留座位。

输入：bookings = [[1,2,10], [2,3,20], [2,5,25]], n = 5
输出：[10, 55, 45, 25, 25]

解释：
航班 1: 10 个座位
航班 2: 10 + 20 + 25 = 55 个座位
航班 3: 20 + 25 = 45 个座位
航班 4: 25 个座位
航班 5: 25 个座位

关键洞察：每个预订就是一次区间更新。差分数组完美适用！

复杂度：O(n + m) 时间，O(n) 空间

面试提示：注意输入是 1 索引！需要转换为 0 索引。

问题三：拼车 (LC 1094)

问题：判断给定容量的汽车能否完成所有行程而不超载。

输入：trips = [[2,1,5], [3,3,7]], capacity = 4
输出：false

解释：
位置 3 处：2 + 3 = 5 个乘客 > 容量 4

关键洞察：使用差分数组作为时间轴跟踪乘客变化！

复杂度：O(max_location) 时间，O(max_location) 空间

为什么有效：

位置：     0  1  2  3  4  5  6  7  8
差分：     0 +2  0 +3  0 -2  0 -3  0
                  ↑     ↑
             上车     下车

应用前缀和（模拟时间轴）：
乘客数：   0  2  2  5  5  3  3  0  0
                   ↑
               超过容量！

问题四：分割正方形 I (LC 3453)

问题：找到一条水平线的最小 y 坐标，使得线上方的正方形总面积等于线下方的总面积。

输入：squares = [[0,0,2],[1,1,1]]
输出：1.16667

解释：
在 y = 7/6 (≈ 1.16667) 处：
- 线下面积：7/6 × 2 + 1/6 = 2.5
- 线上面积：5/6 × 2 + 5/6 = 2.5

关键洞察：使用差分数组配合扫描线算法跟踪每个 y 坐标处的水平边长度！

问题分析

这道题结合了多种高级技巧：

差分数组：跟踪水平边长度的变化
扫描线：从下往上扫描，累计面积
二分查找：在某个线段内找到精确的分割点

理解解法

关键洞察是我们完全不需要关心 x 坐标！我们只需要跟踪：

哪些 y 坐标有边的变化（正方形的开始或结束）
每个 y 高度的总水平边长度
向上扫描时的累计面积

为什么是 `diff[y]` 而不是 `diff[y+1]`？

对于正方形 [x, y, l]：

它覆盖垂直范围 [y, y+l)（左闭右开区间）
在 y 处：水平边长度增加 l
在 y+l 处：水平边长度减少 l

这和拼车问题完全一样！

正方形 [0,0,2]：覆盖 y ∈ [0, 2)

高度：   0    1    2    3
差分：  +2    0   -2    0
        ↑         ↑
      开始      结束

应用前缀和（每个高度的水平边长度）：
边长度：0 → 2 → 2 → 0 → 0

算法步骤

步骤 1：构建差分数组

对每个正方形 [x, y, l]：
  diff[y] += l      // 水平边开始
  diff[y+l] -= l    // 水平边结束

步骤 2：从下往上扫描线

对所有有变化的 y 坐标排序
对每个 y：
  1. 使用当前边长度计算 [preY, y) 的面积
  2. 检查是否到达总面积的一半
  3. 如果是，在 [preY, y) 内二分查找精确分割点
  4. 更新下一段的边长度

步骤 3：二分查找精确分割点

如果 area * 2 >= totArea：
  // 我们已经超过了中点
  // 需要往回退：(area * 2 - totArea) / 2
  // 退回的高度：excess_area / edge_length
  return y - (area * 2 - totArea) / (sumL * 2.0)

复杂度：O(n log n) 时间（排序），O(n) 空间

详细示例演练

输入：squares = [[0,0,2],[1,1,1]]

步骤 1：构建差分数组

正方形 [0,0,2]：diff[0] += 2, diff[2] -= 2
正方形 [1,1,1]：diff[1] += 1, diff[2] -= 1

结果：
diff = {
  0: +2,   // 两条边开始（只有红色正方形）
  1: +1,   // 一条边开始（蓝色正方形）
  2: -3    // 红色和蓝色的边都结束
}

步骤 2：扫描并计算

总面积 = 2×2 + 1×1 = 5
目标 = 5/2 = 2.5

y=0: area = 0 + 0×(0-0) = 0,    sumL = 0+2 = 2
     0 < 2.5，继续
     
y=1: area = 0 + 2×(1-0) = 2,    sumL = 2+1 = 3
     2 < 2.5，继续
     
y=2: area = 2 + 3×(2-1) = 5,    sumL = 3-3 = 0
     5 ≥ 2.5，找到了！
     
     精确位置：
     return 2 - (5×2 - 5) / (3×2.0)
          = 2 - 5/6
          = 7/6
          ≈ 1.16667

可视化：

y 轴
  3 |
  2 |-----------|  ← 边在这里结束
    |    红色    |
  1 |-----+----|  ← 蓝色开始，红色继续
    |     |蓝色|
  0 |-----|----|  ← 红色开始
    0     1    2  x 轴

每个 y 高度的水平边长度：
y ∈ [0,1)：长度 = 2（只有红色）
y ∈ [1,2)：长度 = 3（红色 + 蓝色重叠区域）
y ≥ 2：    长度 = 0

面积计算：
[0,1)：2 × 1 = 2
[1,y]：3 × (y-1)

y 下方总面积：2 + 3(y-1) = 3y - 1
设为一半：3y - 1 = 2.5
         3y = 3.5
          y = 7/6 ≈ 1.16667

为什么有效

差分数组：高效跟踪水平边出现/消失的位置
有序扫描：按顺序处理 y 坐标，维护累计面积
矩形面积公式：面积 = 宽度 × 高度
- 宽度 = 水平边长度之和（sumL）
- 高度 = 垂直距离（y - preY）
线性插值：一旦知道哪个线段包含分割点，就计算精确位置

关键观察

x 坐标无关紧要 — 只有水平投影重要
重叠的正方形多次计数 — 这就是为什么要累加边长度
左闭右开区间 [y, y+l) — 和拼车问题的语义相同
TreeMap/排序键 确保我们按顺序处理 y 坐标

面试技巧

不要过度思考 x 坐标：问题纯粹是关于 y 轴投影
注意重叠：边长度是累加的，不是替换
精度：使用 double 作为最终答案（二分查找给出小数结果）
边界情况：所有正方形都从 y=0 开始？扫描线算法仍然有效！

使用场景对比：前缀和 vs 差分数组

决策矩阵

场景	使用	原因
多次区间查询，少量更新	前缀和	O(1) 查询
多次区间更新，少量查询	差分数组	O(1) 更新
需要频繁查询和更新	线段树	两者都是 O(log n)
静态数组（无更新）	前缀和	简单且快速
只构建一次，查询一次	暴力解法	代码更简单

问题类型识别

使用前缀和的情况：

“求区间 [L, R] 的和”
“统计和为 k 的子数组”
“区间查询”问题
数组是读密集型

使用差分数组的情况：

“给区间 [L, R] 加上值”
“多次预订/预约操作”
“时间轴模拟”
数组是写密集型

复杂度对比

操作	暴力解法	前缀和	差分数组
构建	-	O(n)	O(n)
区间查询	O(n)	O(1) ✓	O(n)
区间更新	O(n)	O(n)	O(1) ✓
最终查询	O(1)	O(1)	O(n)

逆运算关系

差分数组 → 前缀和 → 原数组
  (构建)     (重构)

原数组 → 差分数组 → 最终数组
 (变化)    (应用)     (计算)

常见陷阱

1. 忘记边界元素

❌ 错误：

const diff = new Array(n).fill(0);  // 太小了！
diff[right + 1] -= value;  // 可能越界！

✅ 正确：

const diff = new Array(n + 1).fill(0);  // 边界需要额外空间
diff[right + 1] -= value;  // 安全！

原因：我们需要 diff[right + 1] 来标记区间结束位置。

2. 忘记重构

❌ 错误：

// 对 diff[] 应用更新
rangeUpdate(diff, 0, 2, 5);
return diff;  // 错误！这是差分数组，不是结果！

✅ 正确：

// 对 diff[] 应用更新
rangeUpdate(diff, 0, 2, 5);
return reconstructArray(diff, n);  // 先重构！

3. 索引偏移错误

❌ 错误（当输入是 1 索引时）：

// bookings[i] = [first, last, seats] (1 索引)
diff[first] += seats;  // 错误！应该是 first-1

✅ 正确：

// 转换为 0 索引
diff[first - 1] += seats;
diff[last] -= seats;  // last 已经正确（独占末端）

4. 不理解与前缀和的联系

❌ 错误的思维模型： “差分数组是独立的技术。”

✅ 正确的理解： “差分数组需要前缀和来重构。它们是逆运算！“

5. 不该用的时候用

不要使用差分数组如果：

只有一次区间更新 → 直接用循环
需要在更新之间频繁查询 → 使用线段树
数组很小（< 100）→ 暴力解法就够了

总结

🔑 核心概念

差分数组 = 记录相邻元素之间的变化
前缀和 = 将这些变化累积回原数组

它们是逆运算！

📋 快速参考

操作	时间	空间
构建差分数组	O(n)	O(n)
区间更新	O(1) ✓	-
重构数组	O(n)	-
m 次更新总计	O(n + m)	O(n)

🎯 模式识别

当看到以下关键词时使用差分数组：

“给区间 [L, R] 加上值”
“多次预订操作”
“时间轴模拟”
“区间更新”问题
多次更新，少量最终查询

模板模式：

1. 构建差分数组 (O(n))
2. 应用所有更新 (每次 O(1))
3. 使用前缀和重构 (O(n))

💡 关键要点

前缀和的逆运算：它们互相抵消
O(1) 更新：标记起点和终点，就是这样！
需要重构：最后总是要应用前缀和
边界元素：数组大小是 n + 1
完美适用于区间：当有很多区间操作时

🚀 面试专业技巧

识别模式：“多次区间更新” → 想到差分数组
解释数学：说明前缀和如何重构数组
画出来：可视化差分和重构过程
考虑权衡：解释为什么这比暴力解法好
注意边界：不要忘记 n + 1 大小！

🎯 面试模板：当看到”区间更新”时：

能用差分数组吗？（多次更新，少量查询？）

构建差分数组：diff[i] = arr[i] - arr[i-1]

更新：diff[L] += val; diff[R+1] -= val

重构：应用前缀和

📚 相关主题

前缀和：逆运算 — 两者一起掌握！
线段树：当需要快速更新和查询时
树状数组（Fenwick Tree）：区间操作的替代方案
扫描线算法：类似的基于时间轴的思维

美妙的对称性

数组 → [差分] → 差分数组
差分数组 → [前缀和] → 数组

它们互补！ 🔄

掌握差分数组和前缀和 — 它们是一枚硬币的两面！ 🚀

概述

⏱️ 时间复杂度

💾 空间复杂度

📋 使用场景

🔗 与前缀和的关系

美妙的对称性

可视化对比

核心洞察 💡

构建差分数组

💡 算法

🎮 交互式可视化

Building Difference Array

Initial Array

💻 模板代码

✅ 关键点

O(1) 区间更新 ⚡

💡 神奇公式

为什么有效？

🎮 交互式可视化

Range Update in O(1)

Initial State

💻 模板代码

📊 详细示例

复杂度分析

重构数组

💡 算法

🎮 交互式可视化

Reconstructing Array (Prefix Sum)

After Updates

💻 模板代码

完整工作流程

面试题目

问题一：区间加法 (LC 370) 🔒

问题二：航班预订统计 (LC 1109)

问题三：拼车 (LC 1094)

问题四：分割正方形 I (LC 3453)

问题分析

理解解法

为什么是 diff[y] 而不是 diff[y+1]？

算法步骤

详细示例演练

为什么有效

关键观察

面试技巧

使用场景对比：前缀和 vs 差分数组

决策矩阵

问题类型识别

复杂度对比

逆运算关系

常见陷阱

1. 忘记边界元素

2. 忘记重构

3. 索引偏移错误

4. 不理解与前缀和的联系

5. 不该用的时候用

总结

🔑 核心概念

📋 快速参考

🎯 模式识别

💡 关键要点

🚀 面试专业技巧

📚 相关主题

美妙的对称性

为什么是 `diff[y]` 而不是 `diff[y+1]`？