前缀和
一、什么是前缀和
前缀和（Prefix Sum） 是一种预处理数组的技巧，核心是用空间换时间，把多次区间求和从 O (n) 降到 O (1)。
二、一维前缀和（最常用）
1. 定义
- 原数组：a[1..n]（下标从 1 开始，方便边界）
- 前缀和数组：pre[0..n]
- pre[0] = 0（哨兵，避免判断）
- pre[i] = a[1] + a[2] + … + a[i]（前 i 项和）
2. 递推公式
pre[i] = pre[i-1] + a[i]
3. 区间和公式
求区间 [l, r] 的和：
sum(l, r) = pre[r] – pre[l-1]
4. 示例
原数组：a = [2, 3, -1, 4]（下标 1~4）前缀和：pre = [0, 2, 5, 4, 8]
- sum(1,3) = pre[3] – pre[0] = 4 – 0 = 4
- sum(2,4) = pre[4] – pre[1] = 8 – 2 = 6
5. 复杂度
- 预处理：O (n)
- 单次查询：O (1)
- 空间：O (n)
三、二维前缀和（矩阵）
用于快速求子矩阵和。
1. 定义
- 矩阵：a[1..n][1..m]
- 二维前缀和：pre[i][j] = 左上角 (1,1) 到 (i,j) 的子矩阵和
2. 构建公式
pre[i][j] = pre[i-1][j] + pre[i][j-1] – pre[i-1][j-1] + a[i][j]
3. 子矩阵和公式
求左上角 (x1,y1) 到右下角 (x2,y2) 的和：
sum = pre[x2][y2] – pre[x1-1][y2] – pre[x2][y1-1] + pre[x1-1][y1-1]
四、常见应用
- 多次区间和查询
- 子数组和为 k 的个数
- 最大子数组和（结合动态规划）
- 二维矩阵区域和快速查询
