【每日一题】差分数组

差分数组（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[r+1]-=x

1.2 本质理解

两者配合，恰好让[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) 还原。

💻 代码实现（Python）

whileTrue:try:n,m=map(int,input().split())a=list(map(int,input().split()))# 1. 构建差分数组（0-based）diff=[0]*(n+1)diff[0]=a[0]foriinrange(1,n):diff[i]=a[i]-a[i-1]# 2. 区间修改 → 差分数组单点修改for_inrange(m):x,y,z=map(int,input().split())x,y=x-1,y-1# 转为0-baseddiff[x]+=z diff[y+1]-=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

执行过程：

输出：

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]*(n+1)# 多开一位防止 r+1 越界forfirst,last,seatsinbookings:diff[first-1]+=seats# 左端点（转0-based）diff[last]-=seats# 右端点的下一位# 前缀和还原，diff[n] 是哨兵，不参与结果res=[0]*n res[0]=diff[0]foriinrange(1,n):res[i]=res[i-1]+diff[i]returnres

✅ 详细推演

以示例数据为例：

差分数组变化过程：

初始: [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长度设为n+1，避免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时，车上有 2+3=5 人，超过容量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时已经下车）# 求前缀和过程中检查容量current=0foriinrange(1001):current+=diff[i]ifcurrent>capacity:returnFalsereturnTrue

✅ 推演过程

位置3时车上5人 > capacity=4，返回false。

🎯 关键技巧

• 开区间处理：diff[to] -= num，不是diff[to+1]
• 边还原边判断：不需要存储完整结果数组，节省空间

五、例题 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)加上c：

diff[x1][y1]+=c diff[x1][y2+1]-=c diff[x2+1][y1]-=c diff[x2+1][y2+1]+=c

记忆口诀：左上角加，右上角减，左下角减，右下角加（容斥原理，防止重复计算）

💻 代码实现

n,m,q=map(int,input().split())# 下标从1开始，多开一圈a=[[0]*(m+2)for_inrange(n+2)]diff=[[0]*(m+2)for_inrange(n+2)]# 读入矩阵foriinrange(1,n+1):row=list(map(int,input().split()))forjinrange(1,m+1):a[i][j]=row[j-1]# 构建二维差分数组foriinrange(1,n+1):forjinrange(1,m+1):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,c=map(int,input().split())diff[x1][y1]+=c diff[x1][y2+1]-=c diff[x2+1][y1]-=c diff[x2+1][y2+1]+=c# 二维前缀和还原foriinrange(1,n+1):forjinrange(1,m+1):diff[i][j]+=diff[i-1][j]+diff[i][j-1]-diff[i-1][j-1]print(diff[i][j],end=' ')print()

✅ 详细推演

初始矩阵a：

1 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)加 1

diff 数组变化（仅展示关键位置）：

操作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，但y2+1=5越界不显示

前缀和还原后输出：

2 3 4 1 4 3 4 1 2 2 2 2

🎯 关键技巧

• 下标从1开始：方便处理边界，避免i-1越界
• 多开一圈数组：diff大小设为(n+2)×(m+2)，防止x2+1和y2+1越界
• 容斥公式：右下角+c是为了补回被多减的部分

六、例题 5：字母移位 II

📌 题目描述

给定字符串s（下标从0开始）和shifts[i] = [start, end, direction]：

• direction = 1：将[start, end]区间内字母向后移1位（a→b,z→a）
• direction = 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? 不对，direction=0是向前

🔍 思路分析

这题是差分数组的字符版本。每个操作对区间进行+1或-1，最后统一计算每个位置的累计偏移量，再对26取模。

💻 代码实现

classSolution:defshiftingLetters(self,s:str,shifts:List[List[int]])->str:n=len(s)diff=[0]*(n+1)# 差分数组forstart,end,directioninshifts:delta=1ifdirection==1else-1diff[start]+=delta diff[end+1]-=delta# 前缀和计算每个位置的累计偏移res=[]offset=0foriinrange(n):offset+=diff[i]# 计算新字符：先转数字(0-25)，加偏移，再转回字符num=(ord(s[i])-ord('a')+offset)%26res.append(chr(num+ord('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 前缀和还原偏移量: i=0: offset=0, 'a' + 0 = 'a' i=1: offset=1, 'b' + 1 = 'c' i=2: offset=2, '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]*(n+1)# 多开一位forl,r,valinoperations:diff[l]+=val diff[r+1]-=val# 前缀和还原res=[0]*n res[0]=diff[0]foriinrange(1,n):res[i]=res[i-1]+diff[i]returnres

7.2 二维模板

defdiff2d(n,m,operations):""" operations: List of [x1, y1, x2, y2, val] (1-based, closed) """diff=[[0]*(m+2)for_inrange(n+2)]forx1,y1,x2,y2,valinoperations:diff[x1][y1]+=val diff[x1][y2+1]-=val diff[x2+1][y1]-=val diff[x2+1][y2+1]+=val# 前缀和还原foriinrange(1,n+1):forjinrange(1,m+1):diff[i][j]+=diff[i-1][j]+diff[i][j-1]-diff[i-1][j-1]returndiff

八、适用场景与对比

九、学习心得

差分数组的精髓在于"记录变化，而非状态"。就像记账时不记余额，只记每笔进出，最后统一算总账。

三句话记住差分：

1. 一维两点：diff[l] += x,diff[r+1] -= x
2. 二维四角：左上+，右上-，左下-，右下+
3. 先改后查：所有修改完成后，统一前缀和还原

掌握差分数组后，你会发现很多看似复杂的区间问题，本质上都是"套路题"。