差分数组是前缀和的逆运算，适用于频繁对数组某个区间进行增减操作的场景。
- 暴力做法：每次区间修改 O(n)，m 次操作 O(n*m)
- 差分数组：每次修改 O(1)，最后还原 O(n)，总复杂度 O(n + m)
1
| diff[i] = nums[i] - nums[i-1]
|
| 索引 | 0 | 1 | 2 | 3 | 4 |
|---|
| nums | 2 | 5 | 1 | 4 | 3 |
| diff | 2 | 3 | -4 | 3 | -1 |
对区间 [i, j] 的所有元素 +val：
1
2
| diff[i] += val;
diff[j + 1] -= val; // 注意边界：j+1 不能越界
|
原理：
diff[i] += val → 从 i 开始，后面所有元素都加了 valdiff[j+1] -= val → 从 j+1 开始，抵消前面的增量- 综合效果：只有
[i, j] 区间加了 val
对 diff 做一次前缀和，得到最终的 nums：
1
2
3
4
| res[0] = diff[0];
for (int i = 1; i < n; i++) {
res[i] = res[i - 1] + diff[i];
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Difference {
private:
vector<int> diff;
public:
// 构造差分数组
Difference(vector<int>& nums) {
diff.resize(nums.size());
diff[0] = nums[0];
for (int i = 1; i < nums.size(); i++) {
diff[i] = nums[i] - nums[i - 1];
}
}
// 区间 [i, j] 增加 val（可为负数）
void increment(int i, int j, int val) {
diff[i] += val;
if (j + 1 < diff.size()) {
diff[j + 1] -= val;
}
// j+1 越界说明加到末尾，不用减
}
// 返回最终结果数组
vector<int> result() {
vector<int> res(diff.size());
res[0] = diff[0];
for (int i = 1; i < diff.size(); i++) {
res[i] = res[i - 1] + diff[i];
}
return res;
}
};
|
例题： 假设你有一个长度为 n 的数组，初始都为 0。给你 k 个更新操作，每个操作表示对区间 [start, end] 增加 inc。返回最终数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| vector<int> getModifiedArray(int n, vector<vector<int>>& updates) {
vector<int> diff(n, 0);
for (auto& op : updates) {
int s = op[0], e = op[1], val = op[2];
diff[s] += val;
if (e + 1 < n) diff[e + 1] -= val;
}
// 还原
vector<int> res(n);
res[0] = diff[0];
for (int i = 1; i < n; i++) {
res[i] = res[i - 1] + diff[i];
}
return res;
}
|
LeetCode 1109： 这里有 n 个航班，预订记录 [i, j, k] 表示从 i 到 j 航班增加 k 个座位。返回每个航班的最终预订数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
vector<int> diff(n, 0);
for (auto& b : bookings) {
int first = b[0] - 1; // 注意题目是 1-based
int last = b[1] - 1;
int seats = b[2];
diff[first] += seats;
if (last + 1 < n) diff[last + 1] -= seats;
}
// 前缀和还原
for (int i = 1; i < n; i++) {
diff[i] += diff[i - 1];
}
return diff;
}
|
LeetCode 1094： 车上有 capacity 个空位，乘客上下车，问能不能全部装下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| bool carPooling(vector<vector<int>>& trips, int capacity) {
vector<int> diff(1001, 0); // 站点最多 1000
for (auto& t : trips) {
int num = t[0], from = t[1], to = t[2];
diff[from] += num;
diff[to] -= num; // 到 to 站下车，不用 to+1
}
int cur = 0;
for (int x : diff) {
cur += x;
if (cur > capacity) return false;
}
return true;
}
|
对于矩阵的区间加减，也有二维差分：
1
2
3
4
5
6
7
| // 对矩形 (x1,y1) ~ (x2,y2) 加 val
diff[x1][y1] += val;
diff[x2 + 1][y1] -= val;
diff[x1][y2 + 1] -= val;
diff[x2 + 1][y2 + 1] += val;
// 最后做二维前缀和还原
|
| 题目 | 类型 | 难度 |
|---|
| 370. 区间加法 | 模板题 | 中等 |
| 1109. 航班预订统计 | 模板题 | 中等 |
| 1094. 拼车 | 差分 + 扫描线 | 中等 |
| 253. 会议室 II | 差分思想 | 中等 |
| 731. 我的日程安排表 II | 差分 + TreeMap | 中等 |
| 598. 范围求和 II | 二维差分变种 | 简单 |
- 判断要不要用差分： 题目出现「多次区间加减，最后求结果」，直接想差分
- 注意下标： 题目给的是 1-based 还是 0-based，要转换
- 边界处理：
j+1 越界时不用减，说明加到末尾 - 不需要还原整个数组： 比如拼车问题，边累加边判断即可
- 数据范围大时： 用 map 存离散的差分点（扫描线思想）
