别再暴力遍历了！用差分数组5分钟搞定LeetCode区间修改题（附Python/Java模板）
差分数组：算法竞赛中的区间修改终极武器
在算法竞赛和编程面试中，我们经常会遇到需要对数组进行频繁区间修改的场景。比如LeetCode 1109题"航班预订统计"，要求处理数万次航班座位预订，每次预订都需要对某个区间内的所有元素进行加减操作。面对这类问题，新手程序员往往会本能地选择暴力遍历，但很快就会发现——当数据量达到10^5级别时，O(n²)的暴力解法必然导致超时。这就是差分数组技术大显身手的时刻。
1. 为什么需要差分数组？
想象你正在开发一个航班座位管理系统。每天有数万条预订记录，每条记录都要求将航班从第L排到第R排的每个座位数加k。采用传统的遍历修改方法：
# 暴力解法示例 seats = [0] * 100000 # 10万个座位 for _ in range(50000): # 5万次预订 L, R, k = input() for i in range(L, R+1): seats[i] += k这样的时间复杂度是O(mn)，当m和n都是10^5量级时，总操作次数将达到恐怖的100亿次！而使用差分数组技术，我们可以将每次区间修改的时间复杂度从O(n)降到O(1)，整体复杂度优化到O(m+n)，操作次数骤降至20万次左右——这正是算法竞赛中区分普通选手与高手的关键技巧。
1.1 差分数组的核心思想
差分数组的精妙之处在于它将对区间内每个元素的修改，转化为对区间端点的两次简单操作。具体原理如下：
给定原数组A，我们构造差分数组B，使得：
- B[0] = A[0]
- B[i] = A[i] - A[i-1] (i > 0)
这样，A[i]实际上就是B[0]到B[i]的前缀和。当我们需要对A的区间[L,R]统一加上值c时，只需：
- B[L] += c （使L之后的所有前缀和都增加c）
- B[R+1] -= c （抵消R之后的前缀和增加）
操作模板：
def update(B, L, R, c): B[L] += c if R+1 < len(B): B[R+1] -= c2. 一维差分实战：LeetCode 1109题解
让我们以LeetCode 1109."航班预订统计"为例，演示差分数组的实际应用。题目要求根据n次航班预订记录，计算每个航班最终被预订的座位数。
2.1 问题重述
- 有n个航班，编号从1到n
- 给定 bookings = [[1,2,10],[2,3,20],[2,5,25]]，每个子数组表示从i到j的航班每个预订k个座位
- 返回每个航班的座位总数
2.2 差分解法步骤
- 初始化差分数组（比原数组长度多1，方便处理边界）
n = 5 diff = [0] * (n + 2) # 多一位防止越界- 处理每个预订记录：
bookings = [[1,2,10],[2,3,20],[2,5,25]] for L, R, k in bookings: diff[L] += k diff[R+1] -= k- 通过前缀和得到结果：
res = [] current = 0 for i in range(1, n+1): current += diff[i] res.append(current) # 输出: [10,55,45,25,25]完整Python解决方案：
def corpFlightBookings(bookings, n): diff = [0] * (n + 2) for L, R, k in bookings: diff[L] += k if R+1 <= n: diff[R+1] -= k res = [] current = 0 for i in range(1, n+1): current += diff[i] res.append(current) return res2.3 复杂度分析
- 时间复杂度：O(m + n)，m次预订处理O(m)，前缀和计算O(n)
- 空间复杂度：O(n)，只需额外差分数组空间
相比暴力解法的O(mn)，当n和m都是1e5时，差分解法仅需约0.2秒，而暴力解法可能需要数小时！
3. 二维差分：矩阵覆盖问题
差分思想可以推广到二维甚至更高维度。考虑这样一个问题：在一个n×n的网格上放置多个矩形地毯，每个地毯用左上角(x1,y1)和右下角(x2,y2)表示，问每个格子被多少地毯覆盖。
3.1 二维差分原理
对于二维数组A，其差分数组B满足：
A[i][j] = sum(B[x][y] for x<=i, y<=j)区间修改操作（将矩形区域加上c）需要调整四个角：
B[x1][y1] += c B[x1][y2+1] -= c B[x2+1][y1] -= c B[x2+1][y2+1] += c3.2 代码实现
def matrix_coverage(n, carpets): # 初始化差分数组 diff = [[0]*(n+2) for _ in range(n+2)] # 处理每个地毯 for x1, y1, x2, y2 in carpets: diff[x1][y1] += 1 diff[x1][y2+1] -= 1 diff[x2+1][y1] -= 1 diff[x2+1][y2+1] += 1 # 计算前缀和得到结果 res = [[0]*n for _ in range(n)] for i in range(n): row_sum = 0 for j in range(n): row_sum += diff[i][j] if i == 0: res[i][j] = row_sum else: res[i][j] = res[i-1][j] + row_sum return res3.3 应用场景
这种二维差分技巧广泛应用于：
- 图像处理中的区域滤镜应用
- 游戏开发中的地图区块更新
- CAD软件中的区域填充操作
4. 差分数组的局限与替代方案
虽然差分数组在区间修改场景下表现出色，但它并非万能钥匙。我们需要了解它的局限性：
- 单点查询效率低：每次查询都需要计算前缀和，O(n)时间
- 不支持动态区间查询：无法高效回答"某个区间和是多少"这类问题
当遇到需要频繁查询的场景时，应考虑以下数据结构：
| 数据结构 | 区间修改 | 单点查询 | 区间查询 | 复杂度 |
|---|---|---|---|---|
| 差分数组 | O(1) | O(n) | O(n) | 简单 |
| 树状数组 | O(logn) | O(logn) | O(logn) | 中等 |
| 线段树 | O(logn) | O(logn) | O(logn) | 复杂 |
选择建议：
- 只有区间修改 + 最后统一查询：差分数组
- 需要边修改边查询：树状数组/线段树
5. 高频面试题与模板代码
为了帮助读者快速掌握差分技巧，我整理了5道经典面试题及其差分解法要点：
5.1 题目列表
- 航班预订统计（LeetCode 1109）
- 拼车（LeetCode 1094）
- 区间加法（LeetCode 370）
- 会议室II（LeetCode 253）
- 学生出勤记录II（LeetCode 552）
5.2 Java差分模板
class Difference { private int[] diff; public Difference(int[] nums) { diff = new int[nums.length + 1]; diff[0] = nums[0]; for (int i = 1; i < nums.length; i++) { diff[i] = nums[i] - nums[i-1]; } } public void increment(int L, int R, int k) { diff[L] += k; if (R+1 < diff.length) { diff[R+1] -= k; } } public int[] result() { int[] res = new int[diff.length-1]; res[0] = diff[0]; for (int i = 1; i < res.length; i++) { res[i] = res[i-1] + diff[i]; } return res; } }5.3 使用示例
int[] nums = {1,3,2,5,8}; Difference df = new Difference(nums); df.increment(1, 3, 2); // 第1到3个元素加2 int[] res = df.result(); // [1,5,4,7,8]6. 差分技巧的扩展应用
差分思想不仅限于数值修改，还可以解决许多看似不相关的问题：
6.1 时间区间统计
问题：统计一天内同时在线人数峰值解法：将每个登录/登出视为区间开始/结束，用差分统计各时间点人数变化
6.2 资源分配优化
问题：服务器负载均衡，确保没有时间段超载解法：用差分数组记录每个时间段的负载变化，然后检查前缀和是否超阈值
6.3 几何覆盖问题
问题：计算多个矩形在平面上的重叠区域解法：对x和y轴分别做差分，然后计算二维前缀和
7. 性能优化技巧
在实际编码竞赛中，差分数组的实现还可以进一步优化：
- 原地操作：不需要额外数组，直接在原数组上计算差分
# 原地差分初始化 for i in range(len(nums)-1, 0, -1): nums[i] -= nums[i-1] # 区间修改 nums[L] += c if R+1 < len(nums): nums[R+1] -= c # 恢复原数组 for i in range(1, len(nums)): nums[i] += nums[i-1]- 边界处理技巧：在数组前后各增加一个虚拟元素，避免条件判断
diff = [0] * (n + 2) # 前后各多一位 # 这样更新时无需检查R+1是否越界- 并行计算：对于超大数组，前缀和计算可以使用并行算法（如work-efficient parallel scan）
8. 从差分到前缀和的思想进阶
差分数组实际上是前缀和思想的逆运算。掌握这种变换思维，可以解决更多复杂问题：
- 多维前缀和：快速计算矩阵子区域和
- 树上前缀和：解决子树统计问题
- 异或差分：处理区间异或操作问题
关键洞察：许多区间操作问题都可以转化为端点操作，这正是差分思想的精髓所在。在最近的编程竞赛中，我多次遇到看似复杂的问题，最终都通过差分技巧优雅解决。比如一道要求统计多个时间区间最大重叠度的问题，用差分解法仅需10行代码，而暴力方法则需要复杂的排序和扫描线算法。