遇到「区间求和」「区间批量加减」，先想这两个。
一维前缀和
# pre[i] 表示 nums[0..i-1] 的和，pre[0] = 0
pre = [0]
for x in nums:
pre.append(pre[-1] + x)
# 区间 [l, r] 的和（下标从 0 开始）
s = pre[r + 1] - pre[l]
查询从 O(n) 降到 O(1)，代价是 O(n) 预处理。
二维前缀和
# pre[i][j] = 左上角 (0,0) 到 (i-1,j-1) 的矩形和
pre[i][j] = (pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + matrix[i-1][j-1])
# 子矩形 (x1,y1) 到 (x2,y2) 的和
s = (pre[x2+1][y2+1] - pre[x1][y2+1] - pre[x2+1][y1] + pre[x1][y1])
画个图记：大矩形减掉上面和左面，加回被重复减的左上角。
差分数组：区间批量加减
「给区间 [l, r] 每个元素都加 3」做 m 次，朴素做法 O(m·n)。差分数组 O(m + n)：
diff = [0] * (n + 1)
diff[l] += 3
diff[r + 1] -= 3 # 只改两个端点
# 最后前缀和还原
for i in range(1, n + 1):
diff[i] += diff[i - 1]
本质：把「区间操作」变成「两个点的操作」。
经典例题套路
| 题型 | 解法 |
|---|---|
| 和为 K 的子数组个数 | 前缀和 + 哈希表计数 |
| 航班预订统计（每单给区间 +1） | 差分 |
| 矩阵区域和 | 二维前缀和 |
| 数组中满足某条件的最长区间 | 前缀和 + 单调性/二分 |
和为 K 的子数组（前缀和 + 哈希）
from collections import defaultdict
def subarray_sum(nums, k):
cnt, cur = 0, 0
seen = defaultdict(int)
seen[0] = 1 # 空前缀
for x in nums:
cur += x
cnt += seen[cur - k] # 之前出现过 cur-k，说明中间这段和为 k
seen[cur] += 1
return cnt
seen[0] = 1 这个初始化最容易漏，漏了就数不到从下标 0 开始的子数组。
楼主 · 2026-09-28 13:21 · 浏览 2
