前缀和与差分数组
第三章：前缀和与差分数组
你有一个包含 100 万个元素的数组，需要回答 10 万次"从第 l 个到第 r 个元素的和是多少"这样的查询。最朴素的方法——每次从 l 加到 r——总计算量是 10¹¹ 级别的操作。但如果你花 O(n) 的时间做一次预处理，之后每次查询就只需要 O(1)。这不是什么高深的魔法，而是一个简单到令人发指的想法：把前面所有数加起来存好。
前缀和与差分数组是算法世界中"空间换时间"最优雅的例证之一。它们不需要复杂的数据结构，不需要高级数学，只需要一个加法和一个减法。但正是这种极致的简单性，让它们成为面试中频繁出现的陷阱——因为简单的概念往往导致微妙的实现错误。
Level 1 · 你需要知道的
3.1 前缀和的基本思想
核心理念：如果你提前知道"从开头到任意位置的累加和"，那么"任意区间的和"就可以通过两个预计算值相减得到。
想象你在看一条高速公路上的里程碑。里程碑告诉你从起点到当前位置的距离。如果你想知道从第 30 公里到第 75 公里的距离，不需要重新测量——只需要用 75 公里的里程碑减去 30 公里的里程碑：75 - 30 = 45 公里。
前缀和就是这样的"里程碑"。
给定一个数组 nums，其前缀和数组 prefix 定义为：
prefix[0] = 0
prefix[1] = nums[0]
prefix[2] = nums[0] + nums[1]
...
prefix[i] = nums[0] + nums[1] + ... + nums[i-1]
即 prefix[i] 表示原数组前 i 个元素的和。注意我们定义 prefix[0] = 0，这样 prefix 数组的长度是 n+1，其中 n 是原数组的长度。
3.2 一维前缀和：构建与查询
构建前缀和数组：
def build_prefix_sum(nums: list[int]) -> list[int]:
"""构建前缀和数组。prefix[i] = sum(nums[0..i-1])"""
n = len(nums)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + nums[i]
return prefix
时间复杂度：O(n)，只遍历一次。 空间复杂度：O(n)，存储前缀和数组。
区间查询：
查询 nums[l..r]（包含两端）的和：
def range_sum(prefix: list[int], l: int, r: int) -> int:
"""查询 nums[l..r] 的和，O(1)"""
return prefix[r + 1] - prefix[l]
为什么是 prefix[r+1] - prefix[l]？
prefix[r+1] = nums[0] + nums[1] + ... + nums[r]
prefix[l] = nums[0] + nums[1] + ... + nums[l-1]
相减得到： nums[l] + nums[l+1] + ... + nums[r]
这就是我们想要的区间 [l, r] 的和。
完整示例：
nums = [3, 1, 4, 1, 5, 9, 2, 6]
prefix = build_prefix_sum(nums)
# prefix = [0, 3, 4, 8, 9, 14, 23, 25, 31]
# 查询 nums[2..5] = 4 + 1 + 5 + 9 = 19
print(range_sum(prefix, 2, 5)) # prefix[6] - prefix[2] = 23 - 4 = 19
3.3 性能对比：为什么前缀和重要
假设数组长度 n = 10⁶，查询次数 q = 10⁵：
| 方法 | 预处理 | 单次查询 | 总时间 |
|---|---|---|---|
| 暴力累加 | O(1) | O(n) | O(q × n) = 10¹¹ |
| 前缀和 | O(n) | O(1) | O(n + q) = 10⁶ + 10⁵ |
差距是 10 万倍。这就是为什么任何涉及"多次区间和查询"的场景，前缀和都是你的第一反应。
3.4 二维前缀和：矩阵区域和查询
当数据从一维扩展到二维，前缀和的思想同样适用。给定一个 m×n 的矩阵，我们想快速查询任意矩形区域内元素的和。
定义：prefix[i][j] 表示从矩阵左上角 (0,0) 到 (i-1, j-1) 组成的矩形区域内所有元素的和。
构建：
def build_2d_prefix_sum(matrix: list[list[int]]) -> list[list[int]]:
"""构建二维前缀和。prefix[i][j] = sum of matrix[0..i-1][0..j-1]"""
if not matrix or not matrix[0]:
return [[]]
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] = (matrix[i][j]
+ prefix[i][j+1]
+ prefix[i+1][j]
- prefix[i][j])
return prefix
容斥原理：构建过程中，prefix[i+1][j+1] 等于当前元素加上"上方的前缀和"和"左方的前缀和"，再减去"左上方的前缀和"（因为它被加了两次）。
用图形化方式理解：
+-------+-------+
| | |
| A | B |
| | |
+-------+-------+
| | |
| C | D |
| | |
+-------+-------+
prefix(D的右下角) = A + B + C + D
prefix(B的右下角) = A + B
prefix(C的右下角) = A + C
prefix(A的右下角) = A
所以：D = prefix(D右下) - prefix(B右下) - prefix(C右下) + prefix(A右下)
查询：查询矩形区域 (r1, c1) 到 (r2, c2) 内元素的和：
def range_sum_2d(prefix: list[list[int]], r1: int, c1: int, r2: int, c2: int) -> int:
"""查询 matrix[r1..r2][c1..c2] 的和，O(1)"""
return (prefix[r2+1][c2+1]
- prefix[r1][c2+1]
- prefix[r2+1][c1]
+ prefix[r1][c1])
完整示例：
matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
prefix = build_2d_prefix_sum(matrix)
# 查询 (1,1) 到 (2,2) 的区域和: 5+6+8+9 = 28
print(range_sum_2d(prefix, 1, 1, 2, 2)) # 28
3.5 差分数组：区间修改的利器
问题：给定一个数组，对其进行 q 次区间修改操作（把 [l, r] 范围内每个元素都加上 val），最后输出修改后的数组。
朴素方法：每次操作遍历 [l, r]，总时间 O(q × n)。
差分数组是前缀和的逆运算。如果前缀和是"累加"，那差分就是"拆解"。
定义：给定数组 nums，其差分数组 diff 为：
diff[0] = nums[0]
diff[i] = nums[i] - nums[i-1] (i >= 1)
关键性质：对差分数组求前缀和，就能还原原数组。
nums[0] = diff[0]
nums[1] = diff[0] + diff[1]
nums[2] = diff[0] + diff[1] + diff[2]
...
nums[i] = sum(diff[0..i])
区间修改的 O(1) 实现：
要让 nums[l..r] 每个元素都加上 val，只需：
diff[l] += val
if r + 1 < n:
diff[r + 1] -= val
为什么这样做是正确的？因为当我们最后对 diff 求前缀和还原数组时：
diff[l] += val使得从位置 l 开始，后面所有位置都多加了 valdiff[r+1] -= val使得从位置 r+1 开始，把多加的 val 减回去
效果：只有 [l, r] 范围内的元素被加了 val。
完整实现：
def range_add(n: int, operations: list[tuple[int, int, int]]) -> list[int]:
"""
对长度为 n 的全零数组执行多次区间加操作。
operations: [(l, r, val), ...] 表示对 [l, r] 每个元素加 val
返回最终数组。
"""
diff = [0] * n
for l, r, val in operations:
diff[l] += val
if r + 1 < n:
diff[r + 1] -= val
# 还原：对差分数组求前缀和
result = [0] * n
result[0] = diff[0]
for i in range(1, n):
result[i] = result[i - 1] + diff[i]
return result
# 示例
# 对长度为 6 的数组做三次操作：
# [1,3] +2, [2,5] +3, [0,2] -1
ops = [(1, 3, 2), (2, 5, 3), (0, 2, -1)]
print(range_add(6, ops))
# [-1, 1, 4, 5, 3, 3]
# 验证：初始 [0,0,0,0,0,0]
# +2 on [1,3]: [0,2,2,2,0,0]
# +3 on [2,5]: [0,2,5,5,3,3]
# -1 on [0,2]: [-1,1,4,5,3,3] ✓
3.6 常见错误
错误一：下标 off-by-one
前缀和最容易犯的错误就是下标偏差。记住这个核心公式：
# 区间 [l, r] 的和（左闭右闭）
sum_lr = prefix[r + 1] - prefix[l]
常见错误写法：
# 错误！这会少算 nums[l]
sum_lr = prefix[r] - prefix[l]
# 错误！这会多算 nums[r+1]（如果 r+1 < n）
sum_lr = prefix[r + 1] - prefix[l - 1] # 当 l=0 时还会越界
技巧：prefix 数组多开一位（长度 n+1），让 prefix[0] = 0。这样就不需要处理 l=0 的特殊情况。
错误二：整数溢出
在 Python 中，整数没有溢出问题（Python 的 int 是任意精度的）。但如果你用 C++/Java/Go 等语言：
# Python 没问题
nums = [10**9] * 100000
prefix = build_prefix_sum(nums) # prefix[-1] = 10^14，Python 轻松处理
# C++ 中如果用 int（32位），10^14 远超 2^31 - 1 ≈ 2.1 × 10^9
# 必须用 long long
错误三：差分数组边界处理
# 当 r 是数组最后一个元素时，r+1 = n，不需要减
diff[l] += val
if r + 1 < n: # 这个判断不能忘！
diff[r + 1] -= val
Level 2 · 你需要深入理解的
3.7 前缀和的变体
前缀和的核心思想——"预处理前缀信息以加速区间查询"——可以推广到任何具有逆运算的运算符。
前缀异或：
异或（XOR）满足 a ^ a = 0 和 a ^ 0 = a，所以异或有"自己消自己"的性质，相当于加法中的"减法"。
def build_prefix_xor(nums: list[int]) -> list[int]:
"""构建前缀异或数组"""
n = len(nums)
prefix_xor = [0] * (n + 1)
for i in range(n):
prefix_xor[i + 1] = prefix_xor[i] ^ nums[i]
return prefix_xor
def range_xor(prefix_xor: list[int], l: int, r: int) -> int:
"""查询 nums[l..r] 的异或值"""
return prefix_xor[r + 1] ^ prefix_xor[l]
为什么可以用异或做"前缀和"？因为 XOR 是它自己的逆运算：a ^ b ^ b = a。所以 prefix_xor[r+1] ^ prefix_xor[l] 就能消除 [0, l-1] 部分的影响。
前缀乘积：
乘法的逆运算是除法。如果数组中没有零，可以构建前缀乘积：
def build_prefix_product(nums: list[int]) -> list[float]:
"""前缀乘积，假设无零元素"""
n = len(nums)
prefix_prod = [1.0] * (n + 1)
for i in range(n):
prefix_prod[i + 1] = prefix_prod[i] * nums[i]
return prefix_prod
def range_product(prefix_prod: list[float], l: int, r: int) -> float:
"""区间乘积"""
return prefix_prod[r + 1] / prefix_prod[l]
但注意：除法有精度问题，且不能处理包含零的情况。LeetCode 238 "除自身以外数组的乘积"就利用了这个限制来设计更巧妙的解法（见 Level 4）。
前缀 GCD：
GCD 没有逆运算，所以不能直接用"右端减左端"来做区间查询。前缀 GCD 只能回答"前 i 个元素的 GCD"这类问题，不能做任意区间查询。这是前缀和技巧的适用边界。
总结——哪些运算可以用前缀和技巧：
| 运算 | 逆运算 | 可做区间查询？ |
|---|---|---|
| 加法 (+) | 减法 (-) | ✓ |
| 异或 (^) | 异或 (^) | ✓ |
| 乘法 (×) | 除法 (÷) | ✓（无零时） |
| 最大值 (max) | 无 | ✗ |
| 最小值 (min) | 无 | ✗ |
| GCD | 无 | ✗ |
对于没有逆运算的运算（max, min, GCD），区间查询需要使用稀疏表（Sparse Table）或线段树。
3.8 子数组和问题：和为 K 的子数组
问题（LeetCode 560）：给定整数数组 nums 和整数 k，找出所有和为 k 的连续子数组的个数。
关键洞察：子数组 [l, r] 的和等于 k，等价于 prefix[r+1] - prefix[l] = k，即 prefix[l] = prefix[r+1] - k。
所以问题变成了：对于每个位置 r，有多少个之前的位置 l 满足 prefix[l] = prefix[r+1] - k？
这是一个"两数之差"的问题，用哈希表可以 O(1) 查询。
from collections import defaultdict
def subarray_sum(nums: list[int], k: int) -> int:
"""
找出和为 k 的连续子数组个数。
时间 O(n)，空间 O(n)。
"""
count = 0
prefix_sum = 0
# 记录每个前缀和出现的次数
# 初始化 {0: 1} 表示"空前缀"的和为 0，出现过一次
freq = defaultdict(int)
freq[0] = 1
for num in nums:
prefix_sum += num
# 如果 prefix_sum - k 之前出现过 c 次
# 说明有 c 个起始位置使得子数组和为 k
count += freq[prefix_sum - k]
freq[prefix_sum] += 1
return count
为什么初始化 freq[0] = 1？
这对应"空前缀"的情况。当 prefix_sum 本身就等于 k 时，意味着从数组开头到当前位置的子数组和恰好为 k。此时我们需要 freq[prefix_sum - k] = freq[0] 为 1。
时间复杂度：O(n)——一次遍历，哈希表操作均摊 O(1)。 空间复杂度：O(n)——哈希表最多存 n 个不同的前缀和。
这个技巧将在第 8 章（哈希表）中再次出现，作为"前缀和 + 哈希表"组合技的核心案例。
3.9 差分数组的实际应用：航班预订统计
问题（LeetCode 1109）：有 n 个航班（编号 1 到 n），给定一系列预订 bookings[i] = [first_i, last_i, seats_i]，表示在航班 first_i 到 last_i（含）上预订了 seats_i 个座位。请返回长度为 n 的数组 answer，其中 answer[i] 是航班 i+1 的预订座位总数。
这是差分数组的经典应用场景：多次区间加，最后一次性还原。
def corp_flight_bookings(bookings: list[list[int]], n: int) -> list[int]:
"""航班预订统计，差分数组解法"""
diff = [0] * n
for first, last, seats in bookings:
# 题目中航班编号从 1 开始，转为 0-indexed
diff[first - 1] += seats
if last < n:
diff[last] -= seats
# 前缀和还原
answer = [0] * n
answer[0] = diff[0]
for i in range(1, n):
answer[i] = answer[i - 1] + diff[i]
return answer
性能分析：
- 预订次数为 m，暴力方法 O(m × n)
- 差分数组方法 O(m + n)
当 m = 2 × 10⁴ 且 n = 2 × 10⁴ 时，暴力 = 4 × 10⁸ 操作（TLE），差分 = 4 × 10⁴ 操作。
3.10 二维差分数组
一维差分处理区间修改，二维差分处理矩形区域修改。
问题：给定 m×n 的矩阵，进行 q 次操作，每次把矩形区域 (r1,c1)-(r2,c2) 内所有元素加 val，最后输出修改后的矩阵。
def apply_2d_range_add(m: int, n: int,
operations: list[tuple[int,int,int,int,int]]) -> list[list[int]]:
"""
二维差分数组处理矩形区域修改。
operations: [(r1, c1, r2, c2, val), ...]
"""
# 构建二维差分数组
diff = [[0] * (n + 1) for _ in range(m + 1)]
for r1, c1, r2, c2, val in operations:
diff[r1][c1] += val
diff[r1][c2 + 1] -= val
diff[r2 + 1][c1] -= val
diff[r2 + 1][c2 + 1] += val
# 还原：二维前缀和
result = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
diff[i][j] += (diff[i-1][j] if i > 0 else 0)
diff[i][j] += (diff[i][j-1] if j > 0 else 0)
diff[i][j] -= (diff[i-1][j-1] if i > 0 and j > 0 else 0)
result[i][j] = diff[i][j]
return result
容斥原理再现：二维差分的修改操作需要在四个点上做标记：
- (r1, c1) 加 val：效果向右下方扩散
- (r1, c2+1) 减 val：阻止向右扩散
- (r2+1, c1) 减 val：阻止向下扩散
- (r2+1, c2+1) 加 val：多减的补回来
这和二维前缀和的容斥原理完全对称。
3.11 前缀和与滑动窗口的关系
前缀和和滑动窗口（第 23 章）解决的是同一类问题——区间/子数组相关的查询——但适用场景不同：
| 维度 | 前缀和 | 滑动窗口 |
|---|---|---|
| 适用条件 | 无限制（可处理负数） | 通常需要单调性（元素非负、子数组和递增等） |
| 查询类型 | 精确值（和为 K） | 满足条件的最长/最短区间 |
| 时间复杂度 | O(n)（配合哈希表） | O(n) |
| 空间复杂度 | O(n)（哈希表/前缀数组） | O(1) 到 O(k) |
经验法则：
- 数组包含负数？→ 前缀和 + 哈希表
- 需要找"和恰好为 K"的子数组？→ 前缀和
- 需要找"和不超过 K 的最长子数组"且元素非负？→ 滑动窗口
- 需要找"包含所有字符的最短子串"？→ 滑动窗口
两者有时可以互相替代，但在有负数的情况下，滑动窗口通常无法使用（因为扩展窗口不一定增加和），此时前缀和是唯一的 O(n) 选择。
Level 3 · 数学与工程视角
3.12 前缀和的数学基础
前缀和本质上是部分和（Partial Sum）的离散版本。在数学中：
$$S_n = \sum_{i=0}^{n-1} a_i$$
区间和则是：
$$\sum_{i=l}^{r} a_i = S_{r+1} - S_l$$
这个等式成立的前提是加法满足结合律和交换律，且减法是加法的逆运算——即加法群 (Z, +) 的性质。
更一般地，如果运算 ⊕ 构成一个群（有单位元、封闭性、结合律、逆元），那么前缀"和"的技巧就可以推广。
- (Z, +) → 前缀和
- (Z, ⊕) where ⊕ = XOR → 前缀异或（因为每个元素是自身的逆元）
- (R⁺, ×) → 前缀乘积（逆元是倒数）
但 (Z, max) 不构成群（max 没有逆运算），所以无法使用前缀和技巧做区间最大值查询。
差分与求和的对偶关系：
差分运算符 Δ 定义为：Δ(f)(i) = f(i) - f(i-1)
前缀和运算符 Σ 定义为：Σ(f)(i) = f(0) + f(1) + ... + f(i)
它们互为逆运算：Σ(Δ(f)) = f 且 Δ(Σ(f)) = f
这与微积分中的微分和积分是完全类比的关系。
3.13 前缀和与积分的类比
| 离散（数组） | 连续（函数） |
|---|---|
| 数组 a[i] | 函数 f(x) |
| 前缀和 S[n] = Σa[i] | 积分 F(x) = ∫f(t)dt |
| 差分 Δa[i] = a[i] - a[i-1] | 导数 f'(x) = df/dx |
| 区间和 = S[r+1] - S[l] | 定积分 = F(b) - F(a) |
| 差分数组还原 = 前缀和 | 不定积分 + 微分 = 恒等 |
这个类比不仅是概念上的——微积分基本定理 ∫[a,b] f(x)dx = F(b) - F(a) 和前缀和公式 sum(l,r) = prefix[r+1] - prefix[l] 在结构上完全一致。
Newton-Leibniz 公式的离散版本就是前缀和区间查询公式。这种统一视角帮助你理解为什么差分和前缀和互为逆运算——就像微分和积分互为逆运算一样。
3.14 前缀和在数据库中的应用
在数据库系统中，前缀和以多种形式出现：
累计聚合（Running Aggregation）：
-- 计算每天的累计销售额
SELECT
date,
daily_sales,
SUM(daily_sales) OVER (ORDER BY date) AS cumulative_sales
FROM sales;
这里的窗口函数 SUM(...) OVER (ORDER BY ...) 本质上就是在计算前缀和。数据库引擎内部通常维护一个累加器，扫描一次数据即可完成——和我们的 build_prefix_sum 一样。
窗口函数中的区间查询：
-- 计算过去 7 天的滑动平均
SELECT
date,
AVG(daily_sales) OVER (
ORDER BY date
ROWS BETWEEN 6 PRECEDING AND CURRENT ROW
) AS moving_avg_7d
FROM sales;
虽然 SQL 窗口函数的语法隐藏了实现细节，但底层很多优化器会使用前缀和的思想：先计算累计和，然后用两个累计和相减来得到任意窗口的和。
物化视图与增量维护：
在数据仓库中，预计算的聚合（物化视图）本质上就是"提前算好前缀信息"。当底层数据变化时，差分思想被用于增量更新——只处理变化量（增量），而不是重新计算整体。
3.15 树上前缀和
当数据结构从线性数组扩展到树形结构，前缀和可以通过 DFS 序实现。
问题：给定一棵带权树，多次查询从根到某节点的路径上所有边权之和（或节点权值之和）。
方法一：DFS 直接预处理距离
def build_tree_prefix(graph: dict, root: int,
weights: dict) -> dict[int, int]:
"""
预处理每个节点到根的路径权值和。
graph: 邻接表
weights: 边权 {(u,v): w}
"""
dist = {root: 0}
stack = [root]
visited = {root}
while stack:
u = stack.pop()
for v in graph[u]:
if v not in visited:
visited.add(v)
edge_weight = weights.get((u, v), weights.get((v, u), 0))
dist[v] = dist[u] + edge_weight
stack.append(v)
return dist
有了从根到每个节点的"前缀和"，两点之间的路径和可以表示为：
def path_sum(dist: dict, lca_func, u: int, v: int) -> int:
"""u 到 v 的路径和 = dist[u] + dist[v] - 2 * dist[LCA(u,v)]"""
ancestor = lca_func(u, v)
return dist[u] + dist[v] - 2 * dist[ancestor]
这里 LCA（最近公共祖先）的角色类似于一维前缀和中的"减去公共前缀"。
方法二：DFS 序 + 一维前缀和
将树展平为 DFS 序列后，子树上的操作可以转化为连续区间上的操作：
def dfs_order(graph: dict, root: int) -> tuple[list[int], dict, dict]:
"""
计算 DFS 序。
返回：(序列, 进入时间 tin, 离开时间 tout)
节点 u 的子树对应区间 [tin[u], tout[u]]
"""
order = []
tin = {}
tout = {}
timer = [0]
visited = set()
def dfs(u):
visited.add(u)
tin[u] = timer[0]
order.append(u)
timer[0] += 1
for v in graph[u]:
if v not in visited:
dfs(v)
tout[u] = timer[0] - 1
dfs(root)
return order, tin, tout
将树展平后，"子树和"变成了"区间和"，就可以直接用一维前缀和来处理。这个技巧在竞赛中非常常见，也是线段树处理树上问题的基础。
3.16 高维前缀和
二维前缀和可以推广到任意维度。在 d 维空间中，容斥原理涉及 2^d 个顶点。
三维前缀和的构建和查询：
def build_3d_prefix_sum(arr, X, Y, Z):
"""三维前缀和"""
prefix = [[[0]*(Z+1) for _ in range(Y+1)] for _ in range(X+1)]
for i in range(X):
for j in range(Y):
for k in range(Z):
prefix[i+1][j+1][k+1] = (arr[i][j][k]
+ prefix[i][j+1][k+1]
+ prefix[i+1][j][k+1]
+ prefix[i+1][j+1][k]
- prefix[i][j][k+1]
- prefix[i][j+1][k]
- prefix[i+1][j][k]
+ prefix[i][j][k])
return prefix
三维容斥有 8 个项（2³ = 8），正负交替。实际工程中，超过三维的前缀和很少见，因为空间复杂度是 O(n^d)，指数级增长。
高维前缀和的实际应用：
- 二维：图像处理中的积分图（Integral Image），用于快速计算矩形区域的像素和/平均值
- 三维：医学影像中的体素（voxel）数据分析，计算立方体区域的统计量
Level 4 · 面试实战
3.17 面试高频题精讲
题目一：和为 K 的子数组（LeetCode 560）
我们在 3.8 节已经给出了解法，这里补充面试中的常见追问。
追问 1：如果数组全是正数，有没有更好的方法？
全是正数意味着前缀和严格递增，可以用滑动窗口（双指针）在 O(1) 空间内完成。但原题包含负数和零，前缀和不单调，滑动窗口失效。
追问 2：能否找到所有和为 K 的子数组（而不只是计数）？
可以，但需要记录每个前缀和出现的位置列表而非仅计数：
from collections import defaultdict
def find_all_subarrays_with_sum_k(nums: list[int], k: int) -> list[tuple[int, int]]:
"""返回所有和为 k 的子数组的 (start, end) 对"""
result = []
prefix_sum = 0
# 记录每个前缀和出现的位置列表
positions = defaultdict(list)
positions[0].append(-1) # 空前缀的"位置"是 -1
for i, num in enumerate(nums):
prefix_sum += num
target = prefix_sum - k
if target in positions:
for start_pos in positions[target]:
result.append((start_pos + 1, i))
positions[prefix_sum].append(i)
return result
注意：最坏情况下（如全为零，k=0），结果数量是 O(n²) 的，所以时间复杂度也是 O(n²)。
题目二：连续的子数组和（LeetCode 523）
问题：给定非负整数数组 nums 和整数 k，判断是否存在长度至少为 2 的连续子数组，使得该子数组元素之和是 k 的倍数。
关键洞察：如果 prefix[j] - prefix[i] 是 k 的倍数（j - i >= 2），等价于 prefix[j] % k == prefix[i] % k。
所以我们用哈希表记录每个"前缀和对 k 取模的余数"第一次出现的位置，如果同一个余数再次出现且间距 >= 2，就找到答案了。
def check_subarray_sum(nums: list[int], k: int) -> bool:
"""
判断是否存在长度 >= 2 的子数组和为 k 的倍数。
时间 O(n)，空间 O(min(n, k))。
"""
# 记录每个余数第一次出现的索引
remainder_index = {0: -1} # 空前缀余数为 0，位置 -1
prefix_sum = 0
for i, num in enumerate(nums):
prefix_sum += num
remainder = prefix_sum % k if k != 0 else prefix_sum
if remainder in remainder_index:
# 确保子数组长度至少为 2
if i - remainder_index[remainder] >= 2:
return True
else:
remainder_index[remainder] = i
return False
注意事项：
- 初始化
{0: -1}处理从开头开始的子数组 - 只记录第一次出现的位置（保证间距最大化）
- k = 0 时需要特殊处理（找连续两个前缀和相同的位置）
题目三：除自身以外数组的乘积（LeetCode 238）
问题：给定数组 nums，返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外所有元素的乘积。要求 O(n) 时间且不使用除法。
思路：answer[i] = 左边所有数的乘积 × 右边所有数的乘积。用前缀乘积和后缀乘积分别计算。
def product_except_self(nums: list[int]) -> list[int]:
"""
除自身以外数组的乘积。
时间 O(n)，空间 O(1)（不计输出数组）。
"""
n = len(nums)
answer = [1] * n
# 第一遍：从左到右，answer[i] = 左边所有数的乘积
left_product = 1
for i in range(n):
answer[i] = left_product
left_product *= nums[i]
# 第二遍：从右到左，乘上右边所有数的乘积
right_product = 1
for i in range(n - 1, -1, -1):
answer[i] *= right_product
right_product *= nums[i]
return answer
为什么不用除法？
- 题目明确禁止
- 如果数组包含零，除法会出错
- 这个解法展示了"前缀和后缀"双向扫描的通用技巧
空间优化：上面的解法只用了一个输出数组和两个变量，空间 O(1)（题目说输出数组不算额外空间）。这比维护两个完整的前缀/后缀数组更优雅。
题目四：航班预订统计（LeetCode 1109）
已在 3.9 节详细讲解。面试追问：
追问：如果不是一次性查询，而是边修改边查询呢？
差分数组适合"所有修改做完再统一查询"的场景。如果需要修改和查询交替进行，就需要更强大的数据结构——线段树（支持 O(log n) 的区间修改和区间查询）或树状数组（Binary Indexed Tree）。
3.18 前缀和的溢出处理
在 C++/Java/Go 等有固定精度整数的语言中，前缀和容易溢出。
场景：数组元素值 |a[i]| ≤ 10⁹，数组长度 n ≤ 10⁵，前缀和最大值约 10¹⁴，超过 32 位整数范围（约 2.1 × 10⁹）但在 64 位范围内（约 9.2 × 10¹⁸）。
Python 优势：Python 整数无溢出，但代价是运算速度更慢（大整数需要更多内存分配和运算）。
取模运算的注意事项：
某些题目要求"答案对 10⁹+7 取模"，此时前缀和也需要取模：
MOD = 10**9 + 7
def build_prefix_sum_mod(nums: list[int]) -> list[int]:
n = len(nums)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = (prefix[i] + nums[i]) % MOD
return prefix
陷阱：取模后的前缀和做减法可能得到负数！
def range_sum_mod(prefix: list[int], l: int, r: int) -> int:
"""取模环境下的区间和"""
return (prefix[r + 1] - prefix[l]) % MOD
# 在 Python 中，% 总是返回非负数，所以这里没问题
# 但在 C++ 中：(-3) % 7 = -3（不是 4），需要手动加 MOD
# C++ 写法: return (prefix[r+1] - prefix[l] % MOD + MOD) % MOD
Python 的 % 行为：(-3) % 7 = 4（Python）vs (-3) % 7 = -3（C++/Java）。Python 的行为在算法题中更方便，但如果你用其他语言，必须注意这个差异。
3.19 前缀和 vs 线段树：静态 vs 动态
| 维度 | 前缀和 | 线段树 |
|---|---|---|
| 预处理时间 | O(n) | O(n) |
| 单次查询 | O(1) | O(log n) |
| 单次修改 | O(n)（需重建） | O(log n) |
| 空间 | O(n) | O(n) |
| 实现复杂度 | 极低（几行代码） | 较高（50-100 行） |
| 适用场景 | 静态数据，只查不改 | 动态数据，修改和查询交替 |
何时用前缀和：
- 数组构建完后不会修改
- 多次区间和查询
- 需要极致的查询性能（O(1) vs O(log n)）
- 简洁性和可维护性很重要
何时用线段树：
- 数据会动态变化（单点修改 + 区间查询）
- 需要区间修改 + 区间查询
- 需要维护非可逆运算（最大值、最小值）的区间信息
决策流程图：
是否有修改操作？
├── 否 → 使用前缀和（O(1) 查询）
└── 是 → 修改频率高吗？
├── 先全部修改，最后一次查询 → 差分数组
└── 修改和查询交替 → 线段树/树状数组
3.20 综合练习与模式识别
模式一：前缀和 + 哈希表（计数类问题）
# 模板：统计满足某种区间性质的子数组个数
def count_subarrays_with_property(nums, target):
count = 0
prefix = 0 # 或其他累积量
seen = defaultdict(int)
seen[0] = 1 # 空前缀
for num in nums:
prefix = update(prefix, num) # 累积操作
# 查找有多少个之前的前缀值满足条件
count += seen[complement(prefix, target)]
seen[prefix] += 1
return count
适用题目：LeetCode 560, 523, 974, 930, 1248
模式二：前缀/后缀双向扫描
# 模板：需要同时知道左右两侧信息
def bidirectional_scan(nums):
n = len(nums)
left_info = compute_prefix(nums) # 从左到右
right_info = compute_suffix(nums) # 从右到左
answer = [0] * n
for i in range(n):
answer[i] = combine(left_info[i], right_info[i])
return answer
适用题目：LeetCode 238, 42（接雨水的前缀max解法）, 135
模式三：差分数组（区间批量修改）
# 模板：多次区间修改 + 最终一次还原
def batch_range_update(n, operations):
diff = [0] * (n + 1) # 多开一位避免边界判断
for l, r, val in operations:
diff[l] += val
diff[r + 1] -= val
# 前缀和还原
for i in range(1, n):
diff[i] += diff[i - 1]
return diff[:n]
适用题目：LeetCode 1109, 1094, 370, 253
3.21 本章总结
前缀和与差分数组是一对互为逆运算的技巧：
- 前缀和：预处理 O(n)，将区间查询加速到 O(1)
- 差分数组：将区间修改压缩到 O(1)，最后 O(n) 还原
它们的适用条件是静态或半静态场景——如果数据频繁变化，需要升级到线段树/树状数组。
关键记忆点：
- 前缀和数组多开一位，prefix[0] = 0
- 区间 [l, r] 的和 = prefix[r+1] - prefix[l]
- 差分数组修改 [l, r]：diff[l] += val, diff[r+1] -= val
- 前缀和 + 哈希表 = 处理"和为 K"类问题的万能组合
- 二维操作用容斥原理：加加减减
下一章我们将学习排序算法。从最简单的冒泡排序到工业级的 Timsort，排序不仅是最基础的算法问题，更是理解分治思想和算法分析的绝佳训练场。