一维前缀和与二维前缀和

前缀和（Prefix Sum）是一种用于高效计算数组区间和的预处理技术，尤其适用于需要频繁查询子数组或子矩阵和的场景。下面详细讲解一维前缀和与二维前缀和的原理、构建方法及应用。

---

一、一维前缀和

1. 定义

• 前缀和数组 prefix 的每个元素 prefix[i] 表示原数组 arr 前 i 个元素的和（通常从 arr[0] 到 arr[i-1]）。
• 例如，原数组 arr = [1, 2, 3, 4]，前缀和数组为 prefix = [0, 1, 3, 6, 10]。

2. 构建方法

• 初始化 prefix[0] = 0。
• 递推公式：
  [
  \text{prefix}[i] = \text{prefix}[i-1] + \text{arr}[i-1]
  ]
• 代码实现：

  vector<int> buildPrefix(vector<int>& arr) {int n = arr.size();vector<int> prefix(n + 1, 0);for (int i = 1; i <= n; i++) {prefix[i] = prefix[i - 1] + arr[i - 1];}return prefix;
  }
  

3. 查询区间和

• 查询区间 [L, R] 的和（左闭右闭区间）：
  [
  \text{sum}(L, R) = \text{prefix}[R+1] - \text{prefix}[L]
  ]
• 示例：
  arr = [1, 2, 3, 4]，求 [1, 2] 的和：
  [
  \text{sum}(1, 2) = \text{prefix}[3] - \text{prefix}[1] = 6 - 1 = 5
  ]

4. 应用场景

• 快速计算子数组的和（时间复杂度 O(1)）。
• 解决滑动窗口问题（如和大于等于目标值的最短子数组）。

---

二、二维前缀和

1. 定义

• 二维前缀和数组 prefix 的每个元素 prefix[i][j] 表示从矩阵左上角 (0,0) 到右下角 (i-1,j-1) 的子矩阵的和。
• 例如，矩阵 matrix = [[1,2],[3,4]]，前缀和数组为：
  [
  \text{prefix} = \begin{bmatrix}
  0 & 0 & 0 \
  0 & 1 & 3 \
  0 & 4 & 10 \
  \end{bmatrix}
  ]

2. 构建方法

• 初始化 prefix[0][0] = 0。
• 递推公式：
  [
  \text{prefix}[i][j] = \text{prefix}[i-1][j] + \text{prefix}[i][j-1] - \text{prefix}[i-1][j-1] + \text{matrix}[i-1][j-1]
  ]
• 代码实现：

  vector<vector<int>> build2DPrefix(vector<vector<int>>& matrix) {int m = matrix.size();int n = matrix[0].size();vector<vector<int>> prefix(m + 1, vector<int>(n + 1, 0));for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + matrix[i-1][j-1];}}return prefix;
  }
  

3. 查询子矩阵和

• 查询子矩阵 (x1, y1) 到 (x2, y2) 的和（左闭右闭区间）：
  [
  \text{sum}(x1, y1, x2, y2) = \text{prefix}[x2+1][y2+1] - \text{prefix}[x1][y2+1] - \text{prefix}[x2+1][y1] + \text{prefix}[x1][y1]
  ]
• 示例：
  matrix = [[1,2,3],[4,5,6],[7,8,9]]，求子矩阵 (1,1) 到 (2,2) 的和：
  [
  \text{sum} = 5 + 6 + 8 + 9 = 28 \
  \text{通过前缀和计算：} \text{prefix}[3][3] - \text{prefix}[1][3] - \text{prefix}[3][1] + \text{prefix}[1][1] = 45 - 6 - 12 + 1 = 28
  ]

4. 应用场景

• 快速计算子矩阵的和（时间复杂度 O(1)）。
• 图像处理中的区域像素和统计。
• 动态规划中的矩阵路径问题。

---

三、对比总结

特性	一维前缀和	二维前缀和
数据结构	一维数组	二维数组
构建复杂度	O(n)	O(mn)
查询复杂度	O(1)	O(1)
核心公式	prefix[i] = prefix[i-1] + arr[i-1]	prefix[i][j] = ...（见上文）
应用问题	子数组和、滑动窗口	子矩阵和、图像处理、动态规划

---

四、经典例题

1. 一维前缀和：

   • LeetCode 303. 区域和检索 - 数组不可变
   • LeetCode 560. 和为 K 的子数组

2. 二维前缀和：

   • LeetCode 304. 二维区域和检索 - 矩阵不可变
   • LeetCode 1292. 元素和小于等于阈值的正方形的最大边长

---

通过掌握前缀和和二维前缀和的原理与实现，可以高效解决许多与区间和相关的算法问题。