前缀和

前缀和（Prefix Sum） 是一种用于快速计算数组区间和的技术。

• 在一维数组中，它可以让你用 O(1) 的时间计算任意区间 [l, r] 的元素和。
• 在二维数组中，它可以让你用 O(1) 的时间计算任意子矩阵的元素和。

前缀和是一种空间换时间的优化手段。

它主要用于解决：

• 快速查询任意区间或子矩阵的和
• 大大减少暴力遍历矩阵的时间复杂度，从 O(n²) → O(1)
• 常用于：
  • 图像处理（图像积分）
  • 动态规划优化（比如最大子矩阵和）
  • 算法竞赛中常用的技巧题、滑动窗口题等

一维前缀和

二维前缀和

二维前缀和的定义

给定一个二维数组 A[i][j]，我们构建一个辅助数组 S[i][j]。

得出的结果表示包含左上角 (1,1) 到右下角 (i,j) 的矩形区域的和。

S[i][j] = A[1][1] + A[1][2] + ... + A[i][j]
        = 从 (1,1) 到 (i,j) 这个矩形区域内所有元素的和

前缀和的构建公式

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

画图理解

为了避免重复加，S[i][j] 需要“加当前值 + 上边 + 左边 - 重复部分”
+---+---+---+
| A | A | A |
+---+---+---+
| A | A | x |  ← 你正在处理这个格子 x = A[i][j]
+---+---+---+