别再暴力遍历了！用差分数组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, R1): seats[i] k这样的时间复杂度是O(mn)当m和n都是10^5量级时总操作次数将达到恐怖的100亿次而使用差分数组技术我们可以将每次区间修改的时间复杂度从O(n)降到O(1)整体复杂度优化到O(mn)操作次数骤降至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之后的所有前缀和都增加cB[R1] - c 抵消R之后的前缀和增加操作模板def update(B, L, R, c): B[L] c if R1 len(B): B[R1] - 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[R1] - k通过前缀和得到结果res [] current 0 for i in range(1, n1): 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 R1 n: diff[R1] - k res [] current 0 for i in range(1, n1): 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 xi, yj)区间修改操作将矩形区域加上c需要调整四个角B[x1][y1] c B[x1][y21] - c B[x21][y1] - c B[x21][y21] c3.2 代码实现def matrix_coverage(n, carpets): # 初始化差分数组 diff [[0]*(n2) for _ in range(n2)] # 处理每个地毯 for x1, y1, x2, y2 in carpets: diff[x1][y1] 1 diff[x1][y21] - 1 diff[x21][y1] - 1 diff[x21][y21] 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会议室IILeetCode 253学生出勤记录IILeetCode 5525.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 (R1 diff.length) { diff[R1] - 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 R1 len(nums): nums[R1] - c # 恢复原数组 for i in range(1, len(nums)): nums[i] nums[i-1]边界处理技巧在数组前后各增加一个虚拟元素避免条件判断diff [0] * (n 2) # 前后各多一位 # 这样更新时无需检查R1是否越界并行计算对于超大数组前缀和计算可以使用并行算法如work-efficient parallel scan8. 从差分到前缀和的思想进阶差分数组实际上是前缀和思想的逆运算。掌握这种变换思维可以解决更多复杂问题多维前缀和快速计算矩阵子区域和树上前缀和解决子树统计问题异或差分处理区间异或操作问题关键洞察许多区间操作问题都可以转化为端点操作这正是差分思想的精髓所在。在最近的编程竞赛中我多次遇到看似复杂的问题最终都通过差分技巧优雅解决。比如一道要求统计多个时间区间最大重叠度的问题用差分解法仅需10行代码而暴力方法则需要复杂的排序和扫描线算法。