差分数组Difference Array是算法竞赛和面试中的高频技巧核心思想是化区间操作为单点操作将 O(n) 的区间修改优化到 O(1)。本文从原理出发结合 5 道经典例题带你彻底掌握差分数组。一、核心原理为什么差分数组这么高效1.1 定义与性质对于一个数组a[]其差分数组diff[]定义为diff[i] a[i] - a[i-1] (i ≥ 2) diff[1] a[1]核心性质前缀和还原a[i] diff[1] diff[2] ... diff[i]区间加法 O(1)将[l, r]全部加上x只需修改两个点diff[l]x diff[r1]-x1.2 本质理解操作含义diff[l] x从位置l开始后面所有元素都加了xdiff[r1] - x从位置r1开始后面所有元素都减回x两者配合恰好让[l, r]区间内净增加x区间外不受影响。这就是容斥思想在一维上的体现。1.3 关键限制⚠️只能先修改后查询无法边修改边查询中间结果。如果需要动态查询请使用线段树或树状数组。二、例题 1区间更新 题目描述给定长度为n的数组a[1..n]执行m次操作每次将[x, y]区间内所有元素加上z。最后输出整个数组。输入格式n m a[1] a[2] ... a[n] x1 y1 z1 x2 y2 z2 ... xm ym zm 思路分析这是差分数组最直白的模板题。暴力做法每次修改 O(n)总复杂度 O(m×n)会超时。使用差分数组可将每次修改降到 O(1)最后统一 O(n) 还原。 代码实现PythonwhileTrue:try:n,mmap(int,input().split())alist(map(int,input().split()))# 1. 构建差分数组0-baseddiff[0]*(n1)diff[0]a[0]foriinrange(1,n):diff[i]a[i]-a[i-1]# 2. 区间修改 → 差分数组单点修改for_inrange(m):x,y,zmap(int,input().split())x,yx-1,y-1# 转为0-baseddiff[x]z diff[y1]-z# 注意越界检查# 3. 前缀和还原原数组a[0]diff[0]foriinrange(1,n):a[i]a[i-1]diff[i]print( .join(map(str,a)))except:break✅ 运行示例输入5 2 1 3 5 6 7 2 4 5 1 3 2执行过程步骤diff 数组说明初始[1, 2, 2, 1, 1, 0]原数组[1,3,5,6,7]的差分操作1[2,4]5[1, 7, 2, 1, -4, 0]diff[1]5,diff[4]-5操作2[1,3]2[3, 7, 2, 1, -4, -2]diff[0]2,diff[3]-2前缀和还原[3, 10, 12, 13, 9, 7]最终数组输出3 10 12 13 9三、例题 2航班预订统计 题目描述有n个航班编号1到n。给定bookings[i] [first, last, seats]表示从航班first到last包含每个航班预订seats个座位。返回每个航班最终的预订总数。示例输入bookings [[1,2,10],[2,3,20],[2,5,25]], n 5 输出[10, 55, 45, 25, 25] 思路分析这是差分数组的经典变形题。题目绕了个弯本质就是初始全0数组对多个闭区间执行加法求最终结果。注意航班编号从1开始而数组下标从0开始需要转换。 代码实现classSolution:defcorpFlightBookings(self,bookings:List[List[int]],n:int)-List[int]:diff[0]*(n1)# 多开一位防止 r1 越界forfirst,last,seatsinbookings:diff[first-1]seats# 左端点转0-baseddiff[last]-seats# 右端点的下一位# 前缀和还原diff[n] 是哨兵不参与结果res[0]*n res[0]diff[0]foriinrange(1,n):res[i]res[i-1]diff[i]returnres✅ 详细推演以示例数据为例航班12345预订1[1,2]101010预订2[2,3]202020预订3[2,5]2525252525总计1055452525差分数组变化过程初始: [0, 0, 0, 0, 0, 0] 操作1: [10, 0, -10, 0, 0, 0] # diff[0]10, diff[2]-10 操作2: [10, 20, -10, -20, 0, 0] # diff[1]20, diff[3]-20 操作3: [10, 45, -10, -20, 0, -25]# diff[1]25, diff[5]-25 前缀和: 10 → 55 → 45 → 25 → 25 关键技巧多开一位数组diff长度设为n1避免diff[last]越界判断闭区间转差分[first, last]对应diff[first-1] seats,diff[last] - seats四、例题 3拼车 题目描述车上有capacity个空座位只能单向行驶。给定trips[i] [num, from, to]表示在from接上num人在to放下。判断能否完成所有行程。示例输入trips [[2,1,5],[3,3,7]], capacity 4 输出false 解释在位置3时车上有 235 人超过容量4 思路分析这题是差分数组的判断型应用。注意区间是左闭右开[from, to)——在to位置乘客已经下车了。我们不需要完全还原数组只需在求前缀和的过程中实时检查是否超载。 代码实现classSolution:defcarPooling(self,trips:List[List[int]],capacity:int)-bool:# 根据数据范围最大位置是1000diff[0]*1001fornum,from_i,to_iintrips:diff[from_i]num# 上车diff[to_i]-num# 下车开区间到to时已经下车# 求前缀和过程中检查容量current0foriinrange(1001):currentdiff[i]ifcurrentcapacity:returnFalsereturnTrue✅ 推演过程位置01234567行程1[2,1,5)2-2行程2[3,3,7)3-3diff02030-20-3前缀和(车上人数)02255330位置3时车上5人 capacity4返回false。 关键技巧开区间处理diff[to] - num不是diff[to1]边还原边判断不需要存储完整结果数组节省空间五、例题 4二维差分——子矩阵加法 题目描述输入n×m矩阵执行q次操作每次将子矩阵(x1,y1)到(x2,y2)内所有元素加上c。输出最终矩阵。输入样例3 4 3 1 2 2 1 3 2 2 1 1 1 1 1 1 1 2 2 1 1 3 2 3 2 3 1 3 4 1 思路分析二维差分是一维的扩展。核心公式diff[i][j] a[i][j] - a[i-1][j] - a[i][j-1] a[i-1][j-1]子矩阵(x1,y1)到(x2,y2)加上cdiff[x1][y1]c diff[x1][y21]-c diff[x21][y1]-c diff[x21][y21]c记忆口诀左上角加右上角减左下角减右下角加容斥原理防止重复计算 代码实现n,m,qmap(int,input().split())# 下标从1开始多开一圈a[[0]*(m2)for_inrange(n2)]diff[[0]*(m2)for_inrange(n2)]# 读入矩阵foriinrange(1,n1):rowlist(map(int,input().split()))forjinrange(1,m1):a[i][j]row[j-1]# 构建二维差分数组foriinrange(1,n1):forjinrange(1,m1):diff[i][j]a[i][j]-a[i-1][j]-a[i][j-1]a[i-1][j-1]# q次区间修改for_inrange(q):x1,y1,x2,y2,cmap(int,input().split())diff[x1][y1]c diff[x1][y21]-c diff[x21][y1]-c diff[x21][y21]c# 二维前缀和还原foriinrange(1,n1):forjinrange(1,m1):diff[i][j]diff[i-1][j]diff[i][j-1]-diff[i-1][j-1]print(diff[i][j],end )print()✅ 详细推演初始矩阵a1 2 2 1 3 2 2 1 1 1 1 1操作1(1,1)到(2,2)加 1操作2(1,3)到(2,3)加 2操作3(3,1)到(3,4)加 1diff 数组变化仅展示关键位置操作1后 diff: 0 0 0 0 0 0 1 0 -1 0 0 0 0 0 0 0 -1 0 1 0 0 0 0 0 0 操作2后 diff: 0 0 0 0 0 0 1 0 1 -2 0 0 0 0 0 0 -1 0 1 0 0 0 0 0 0 操作3后 diff: 0 0 0 0 0 0 1 0 1 -2 0 0 0 0 0 0 -1 0 1 0 0 1 1 1 1 - 最后一行1但y215越界不显示前缀和还原后输出2 3 4 1 4 3 4 1 2 2 2 2 关键技巧下标从1开始方便处理边界避免i-1越界多开一圈数组diff大小设为(n2)×(m2)防止x21和y21越界容斥公式右下角c是为了补回被多减的部分六、例题 5字母移位 II 题目描述给定字符串s下标从0开始和shifts[i] [start, end, direction]direction 1将[start, end]区间内字母向后移1位a→b,z→adirection 0将[start, end]区间内字母向前移1位b→a,a→z返回所有操作后的字符串。示例输入s abc, shifts [[0,1,0],[1,2,1],[0,2,1]] 输出ace 解释 - [0,1,0]: abc → aac (ab后移→aa) - [1,2,1]: aac → abd (ac前移→bd) 不对重新算... 实际上 [0,1,0] 表示 a,b 向前移: a→z? 不对direction0是向前 思路分析这题是差分数组的字符版本。每个操作对区间进行1或-1最后统一计算每个位置的累计偏移量再对26取模。 代码实现classSolution:defshiftingLetters(self,s:str,shifts:List[List[int]])-str:nlen(s)diff[0]*(n1)# 差分数组forstart,end,directioninshifts:delta1ifdirection1else-1diff[start]delta diff[end1]-delta# 前缀和计算每个位置的累计偏移res[]offset0foriinrange(n):offsetdiff[i]# 计算新字符先转数字(0-25)加偏移再转回字符num(ord(s[i])-ord(a)offset)%26res.append(chr(numord(a)))return.join(res)✅ 推演过程s abc, shifts [[0,1,0],[1,2,1],[0,2,1]] 初始: a b c diff: [0, 0, 0, 0] 操作1 [0,1,0](-1): diff: [-1, 0, 1, 0] # diff[0]-1, diff[2]1 操作2 [1,2,1](1): diff: [-1, 1, 1, -1] # diff[1]1, diff[3]-1 操作3 [0,2,1](1): diff: [0, 1, 1, -1] # diff[0]1, diff[3]-1 前缀和还原偏移量: i0: offset0, a 0 a i1: offset1, b 1 c i2: offset2, c 2 e (c→d→e) 结果: ace 关键技巧差分存储偏移量不是直接修改字符而是记录每个位置的净偏移取模运算% 26处理循环移位26再%26防止负数统一转换所有操作完成后一次性计算最终字符七、差分数组模板总结7.1 一维模板defdifference_array(n,operations): operations: List of [l, r, val] (0-based, closed interval) returns: modified array diff[0]*(n1)# 多开一位forl,r,valinoperations:diff[l]val diff[r1]-val# 前缀和还原res[0]*n res[0]diff[0]foriinrange(1,n):res[i]res[i-1]diff[i]returnres7.2 二维模板defdiff2d(n,m,operations): operations: List of [x1, y1, x2, y2, val] (1-based, closed) diff[[0]*(m2)for_inrange(n2)]forx1,y1,x2,y2,valinoperations:diff[x1][y1]val diff[x1][y21]-val diff[x21][y1]-val diff[x21][y21]val# 前缀和还原foriinrange(1,n1):forjinrange(1,m1):diff[i][j]diff[i-1][j]diff[i][j-1]-diff[i-1][j-1]returndiff八、适用场景与对比场景推荐算法时间复杂度多次区间修改 最终查询差分数组O(n m)单点修改 区间查询前缀和O(1)查询区间修改 区间查询在线树状数组/线段树O(log n)二维子矩阵修改 最终查询二维差分O(n×m q)九、学习心得差分数组的精髓在于记录变化而非状态。就像记账时不记余额只记每笔进出最后统一算总账。三句话记住差分一维两点diff[l] x,diff[r1] - x二维四角左上右上-左下-右下先改后查所有修改完成后统一前缀和还原掌握差分数组后你会发现很多看似复杂的区间问题本质上都是套路题。