核心哲学：从“增量遍历”到“快照查询”

前缀和的本质是将 $O(N)$ 的区间求和离线化。普通的遍历求和是“现算现卖”，而前缀和是“预先存好快照”。

1. 一维前缀和：差分的逆运算

• 构造公式：$S[i] = S[i-1] + A[i]$（$O(N)$ 复杂度）
• 查询公式：$[L, R]$ 区间的和为 $S[R] - S[L-1]$（$O(1)$ 复杂度）

严谨细节：建议 $S$ 数组长度设为 $n+1$，令 $S[0] = 0$。这样可以完美避免处理 $L=0$ 时的边界溢出问题。

2. 二维前缀和：容斥原理

在矩阵区域求和中，二维前缀和 $S[i][j]$ 表示从 $(0,0)$ 到 $(i,j)$ 矩形区域的总和。

• 递推构造：

  $$S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + A[i][j]$$

• 子矩形查询：

  $$Sum = S[x_2][y_2] - S[x_1-1][y_2] - S[x_2][y_1-1] + S[x_1-1][y_1-1]$$

Python 工程实践 (uv 视角)

利用 itertools.accumulate 是实现一维前缀和最快、最优雅的方式：

1
2
3
4
5

from itertools import accumulate

def get_prefix_sum(data: list[int]) -> list[int]:
    # 增加首位 0 以处理边界
    return [0] + list(accumulate(data))