30 秒速览
- 什么时候用：频繁查询区间和、频繁对区间做加减操作
- 核心思想：预处理让后续操作 O(1)
- 时间复杂度：预处理 O(n)，查询/修改 O(1)
- 空间复杂度：O(n)
一、直觉建立
银行余额查询
想象你是银行柜员，要频繁查询某段时间的交易总额。
笨办法：每次都从第一天加到最后一天，O(n)
聪明办法：提前算好"从开户到每一天的累计金额"，然后用减法快速得到任意区间的总额，O(1)
区间 [L, R] 的和 = 累计到 R 的总额 - 累计到 L-1 的总额
= prefix[R+1] - prefix[L]
前缀和的本质
前缀和 = 预计算 + 空间换时间
原数组: nums = [1, 2, 3, 4, 5]
前缀和: prefix = [0, 1, 3, 6, 10, 15]
↑ ↑ ↑ ↑ ↑ ↑
空 1 1+2 ...
区间 [1, 3] 的和 = prefix[4] - prefix[1] = 10 - 1 = 9
即 nums[1] + nums[2] + nums[3] = 2 + 3 + 4 = 9
二、前缀和模板
一维前缀和
def build_prefix(nums: list[int]) -> list[int]:
"""构建前缀和数组"""
n = len(nums)
prefix = [0] * (n + 1) # prefix[0] = 0 表示空前缀
for i in range(n):
prefix[i + 1] = prefix[i] + nums[i]
return prefix
def range_sum(prefix: list[int], left: int, right: int) -> int:
"""查询区间 [left, right] 的和，O(1)"""
return prefix[right + 1] - prefix[left]
为什么用 n+1 长度？
prefix[0] = 0 （空前缀，方便计算从开头到某位置的和）
prefix[1] = nums[0]
prefix[2] = nums[0] + nums[1]
...
prefix[i] = nums[0] + nums[1] + ... + nums[i-1]
这样区间 [L, R] 的和 = prefix[R+1] - prefix[L]
二维前缀和
def build_prefix_2d(matrix: list[list[int]]) -> list[list[int]]:
"""构建二维前缀和"""
m, n = len(matrix), len(matrix[0])
prefix = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m):
for j in range(n):
prefix[i+1][j+1] = (prefix[i][j+1] + prefix[i+1][j]
- prefix[i][j] + matrix[i][j])
return prefix
def region_sum(prefix: list[list[int]], r1: int, c1: int, r2: int, c2: int) -> int:
"""查询矩阵区域 [r1,c1] 到 [r2,c2] 的和"""
return (prefix[r2+1][c2+1] - prefix[r1][c2+1]
- prefix[r2+1][c1] + prefix[r1][c1])
二维前缀和图解：
要求区域 (r1,c1) 到 (r2,c2) 的和：
┌──────────────────────┐
│ │ c1 │
│ A │ c2 │
│ │ B │
├────────┼─────────────┤
│ r1 │ 目标区域 │
│ r2 │ D │
│ │ C │
└──────────────────────┘
目标区域 = 总面积 - A - B - C + (A与B与C重叠部分)
= prefix[r2+1][c2+1]
- prefix[r1][c2+1] (减去上方)
- prefix[r2+1][c1] (减去左方)
+ prefix[r1][c1] (加回左上角多减的部分)
三、典型例题
例题 1：LC 303. 区域和检索 - 数组不可变
题目：给定一个整数数组 nums，处理以下类型的多个查询：计算索引 left 和 right 之间的 nums 元素的和（包含 left 和 right）。
代码
class NumArray:
def __init__(self, nums: list[int]):
n = len(nums)
self.prefix = [0] * (n + 1)
for i in range(n):
self.prefix[i + 1] = self.prefix[i] + nums[i]
def sumRange(self, left: int, right: int) -> int:
return self.prefix[right + 1] - self.prefix[left]
复杂度：初始化 O(n)，查询 O(1)
例题 2：LC 560. 和为 K 的子数组（重点）
题目：给你一个整数数组 nums 和一个整数 k，请你统计并返回该数组中和为 k 的连续子数组的个数。
示例：
输入：nums = [1,1,1], k = 2
输出：2
思路分析
为什么不能用滑动窗口？
滑动窗口需要单调性：窗口扩大时，和单调增加。但如果数组有负数，窗口扩大时和可能减小！
前缀和 + 哈希表：
设 prefix[i] 表示 nums[0..i-1] 的和
子数组 [j, i-1] 的和 = prefix[i] - prefix[j]
问题转化：找有多少对 (j, i) 使得 prefix[i] - prefix[j] = k
即：prefix[j] = prefix[i] - k
代码
from collections import defaultdict
def subarraySum(nums: list[int], k: int) -> int:
count = defaultdict(int)
count[0] = 1 # 空前缀，处理从开头到某位置恰好等于 k 的情况
prefix_sum = 0
result = 0
for num in nums:
prefix_sum += num
# 找之前有多少个前缀和等于 prefix_sum - k
result += count[prefix_sum - k]
count[prefix_sum] += 1
return result
图解
nums = [1, 1, 1], k = 2
遍历过程：
i=0: prefix_sum=1, 需要找 prefix_sum-k=-1, count[-1]=0, result=0
count = {0:1, 1:1}
i=1: prefix_sum=2, 需要找 prefix_sum-k=0, count[0]=1, result=1
count = {0:1, 1:1, 2:1}
i=2: prefix_sum=3, 需要找 prefix_sum-k=1, count[1]=1, result=2
count = {0:1, 1:1, 2:1, 3:1}
最终: result=2
复杂度：时间 O(n)，空间 O(n)
例题 3：LC 1248. 统计「优美子数组」
题目：给你一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。请返回优美子数组的数量。
思路
把奇数位置记录下来，问题转化为：在奇数位置数组中找区间。
def numberOfSubarrays(nums: list[int], k: int) -> int:
# 记录所有奇数的位置（在原数组中的索引+1）
odd_indices = [0] # 前置一个 0，方便计算
for i, num in enumerate(nums, 1):
if num % 2 == 1:
odd_indices.append(i)
# 统计优美子数组数量
result = 0
for i in range(k, len(odd_indices)):
# 奇数区间 [i-k+1, i]
# 左边可选的偶数个数 = odd_indices[i-k+1] - odd_indices[i-k]
# 右边可选的偶数个数 = odd_indices[i+1] - odd_indices[i]（如果有）
left = odd_indices[i - k + 1] - odd_indices[i - k]
right = (odd_indices[i + 1] if i + 1 < len(odd_indices)
else len(nums) + 1) - odd_indices[i]
result += left * right
return result
例题 4：LC 304. 二维区域和检索
题目：给定一个二维矩阵 matrix，实现 NumMatrix 类，支持查询子矩形范围内元素的总和。
代码
class NumMatrix:
def __init__(self, matrix: list[list[int]]):
m, n = len(matrix), len(matrix[0])
self.prefix = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m):
for j in range(n):
self.prefix[i+1][j+1] = (self.prefix[i][j+1] +
self.prefix[i+1][j] -
self.prefix[i][j] +
matrix[i][j])
def sumRegion(self, r1: int, c1: int, r2: int, c2: int) -> int:
return (self.prefix[r2+1][c2+1] - self.prefix[r1][c2+1] -
self.prefix[r2+1][c1] + self.prefix[r1][c1])
复杂度：初始化 O(mn)，查询 O(1)
例题 5：LC 238. 除自身以外数组的乘积
题目：给你一个整数数组 nums，返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。不能使用除法。
示例：
输入: nums = [1,2,3,4]
输出: [24,12,8,6]
思路：前缀积 + 后缀积
对于位置 i:
answer[i] = (左边所有元素的乘积) × (右边所有元素的乘积)
= prefix[i-1] × suffix[i+1]
代码
def productExceptSelf(nums: list[int]) -> list[int]:
n = len(nums)
answer = [1] * n
# 计算左边的乘积
prefix = 1
for i in range(n):
answer[i] = prefix
prefix *= nums[i]
# 计算右边的乘积，同时更新答案
suffix = 1
for i in range(n - 1, -1, -1):
answer[i] *= suffix
suffix *= nums[i]
return answer
图解
nums = [1, 2, 3, 4]
第一遍（计算左边乘积）:
i=0: answer[0] = 1
i=1: answer[1] = 1
i=2: answer[2] = 1*2 = 2
i=3: answer[3] = 1*2*3 = 6
answer = [1, 1, 2, 6]
第二遍（计算右边乘积）:
i=3: answer[3] = 6 * 1 = 6
i=2: answer[2] = 2 * 4 = 8
i=1: answer[1] = 1 * 3*4 = 12
i=0: answer[0] = 1 * 2*3*4 = 24
answer = [24, 12, 8, 6]
复杂度：时间 O(n)，空间 O(1)（输出数组不算额外空间）
四、差分数组
差分数组的本质
差分数组 = 前缀和的逆操作
- 前缀和：从原数组计算前缀和，支持 O(1) 区间查询
- 差分数组：从原数组计算差分，支持 O(1) 区间修改
原数组: nums = [1, 3, 6, 10, 15]
差分数组: diff = [1, 2, 3, 4, 5]
↑ ↑ ↑ ↑ ↑
首 差值 差值 差值 差值
diff[0] = nums[0]
diff[i] = nums[i] - nums[i-1] (i > 0)
还原: nums[i] = sum(diff[0..i])
差分数组模板
def build_diff(nums: list[int]) -> list[int]:
"""构建差分数组"""
n = len(nums)
diff = [0] * n
diff[0] = nums[0]
for i in range(1, n):
diff[i] = nums[i] - nums[i - 1]
return diff
def range_add(diff: list[int], left: int, right: int, val: int):
"""区间 [left, right] 加上 val，O(1)"""
diff[left] += val
if right + 1 < len(diff):
diff[right + 1] -= val
def restore(diff: list[int]) -> list[int]:
"""从差分数组还原原数组"""
result = []
curr = 0
for d in diff:
curr += d
result.append(curr)
return result
为什么差分数组能 O(1) 区间修改？
对区间 [2, 4] 加上 3：
原数组: [1, 3, 6, 10, 15]
期望结果: [1, 3, 9, 13, 18]
↑ ↑ ↑
+3 +3 +3
差分数组原: [1, 2, 3, 4, 5]
差分数组改: [1, 2, 6, 4, 2]
↑ diff[2] += 3
↑ diff[5] -= 3（超出范围则不需要）
还原:
i=0: 1
i=1: 1+2=3
i=2: 3+6=9 ← 从这里开始多了 3
i=3: 9+4=13
i=4: 13+2=15 ← 从这里开始恢复正常（因为 diff[5]-=3 抵消了）
结果: [1, 3, 9, 13, 15]... 等等，这里有问题
关键理解：
diff[left] += val：从 left 位置开始，所有后续元素都多了 valdiff[right+1] -= val：从 right+1 位置开始，抵消之前加的 val
例题 6：LC 1109. 航班预订统计
题目：这里有 n 个航班，分别从 1 到 n 编号。有一份航班预订表 bookings，其中 bookings[i] = [firsti, lasti, seatsi] 表示在从 firsti 到 lasti 的每个航班上预订了 seatsi 个座位。返回一个长度为 n 的数组 answer，表示每个航班预订的座位总数。
示例：
输入: bookings = [[1,2,10],[2,3,20]], n = 3
输出: [10, 55, 20]... 等等，让我重新计算
航班1: 10
航班2: 10 + 20 = 30
航班3: 20
输出: [10, 30, 20]
代码
def corpFlightBookings(bookings: list[list[int]], n: int) -> list[int]:
diff = [0] * (n + 1)
# 构建差分数组
for first, last, seats in bookings:
diff[first] += seats
if last + 1 <= n:
diff[last + 1] -= seats
# 前缀和还原答案
answer = []
curr = 0
for i in range(1, n + 1):
curr += diff[i]
answer.append(curr)
return answer
复杂度：时间 O(n + m)，空间 O(n)，m 是预订数量
例题 7：LC 1094. 拼车
题目：假设你是一位顺风车司机，车上最初有 capacity 个空座位。车只能向一个方向行驶。给定行程 trips，其中 trips[i] = [numPassengersi, fromi, toi] 表示第 i 次行程有 numPassengersi 名乘客，在 fromi 上车，在 toi 下车。判断是否能接送所有乘客。
代码
def carPooling(trips: list[list[int]], capacity: int) -> bool:
# 找最远的位置
max_loc = max(trip[2] for trip in trips)
diff = [0] * (max_loc + 1)
for passengers, start, end in trips:
diff[start] += passengers
diff[end] -= passengers # 在 end 位置下车
curr = 0
for d in diff:
curr += d
if curr > capacity:
return False
return True
复杂度：时间 O(n + m)，空间 O(m)
五、前缀和 + 哈希表 模式总结
适用场景：统计满足某条件的子数组个数
from collections import defaultdict
def count_subarrays(nums: list[int], condition) -> int:
count = defaultdict(int)
count[0] = 1 # 空前缀
prefix = 0
result = 0
for num in nums:
prefix += num # 或其他累加方式
# 根据条件查找需要的前缀和
target = ... # 根据 prefix 和 condition 计算
result += count[target]
count[prefix] += 1
return result
常见变体：
| 问题 | 查找条件 |
|---|---|
| 和为 K 的子数组 | count[prefix - k] |
| 和能被 K 整除的子数组 | count[prefix % k] |
| 和为奇数的子数组 | count[prefix % 2] |
六、复盘清单
触发信号
- 频繁查询区间和（前缀和）
- 频繁对区间做加减操作（差分数组）
- 统计满足某条件的子数组个数（前缀和 + 哈希表）
边界条件
- 空数组
- 单元素
- 负数（滑动窗口失效，用前缀和+哈希）
- 前缀和溢出（Python 自动处理大整数）
常见错误
- 前缀和数组长度搞错（应该是 n+1）
- 区间公式下标错误（[L,R] = prefix[R+1] - prefix[L]）
- 忘记初始化 count[0] = 1
- 差分数组还原时忘记处理边界
七、题目清单
前缀和
| 题号 | 题目 | 难度 | 考点 |
|---|---|---|---|
| 303 | 区域和检索 | Easy | 一维前缀和 |
| 304 | 二维区域和检索 | Medium | 二维前缀和 |
| 560 | 和为 K 的子数组 | Medium | 前缀和+哈希 |
| 974 | 和可被 K 整除的子数组 | Medium | 前缀和+哈希 |
| 1248 | 统计优美子数组 | Medium | 前缀和变形 |
| 238 | 除自身以外数组的乘积 | Medium | 前缀积 |
差分数组
| 题号 | 题目 | 难度 | 考点 |
|---|---|---|---|
| 1109 | 航班预订统计 | Medium | 差分数组 |
| 1094 | 拼车 | Medium | 差分数组 |
| 370 | 区间加法 | Medium | 差分数组 |