二维前缀和是一种针对矩阵区域和查询场景的高效优化算法，它的核心思路是提前预处理出一个前缀和数组，这个数组的每个元素表示原矩阵中从左上角到当前位置构成的矩形区域内所有元素的总和，后续进行区域和查询时只需要通过简单的四则运算就能得到结果，不需要重复遍历区域元素。
二维前缀和的核心原理
假设我们有一个m行n列的原矩阵matrix，我们构建对应的前缀和数组prefix，其中prefix[i][j]表示原矩阵中从第0行第0列到第i-1行第j-1列这个矩形区域内所有元素的总和。这里前缀和数组的行列数比原矩阵多1，是为了方便处理边界情况，比如查询从第一行第一列开始的矩形区域时不需要额外做边界判断。
前缀和数组的递推公式为：
prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + matrix[i-1][j-1]
这个公式的逻辑是，当前矩形区域的和等于上方矩形区域的和加上左方矩形区域的和，再减去重复计算的上方左方重叠区域的和，最后加上当前原矩阵对应位置的元素。
区域和查询的计算方法
当我们需要查询原矩阵中从第x1行第y1列到第x2行第y2列（行和列都是从0开始计数）的矩形区域和时，可以通过以下公式快速计算：
区域和 = prefix[x2+1][y2+1] - prefix[x1][y2+1] - prefix[x2+1][y1] + prefix[x1][y1]
这个公式的原理和前缀和数组的递推逻辑类似，用大的矩形区域减去多余的两个矩形区域，再加上被重复减去的重叠区域，就能得到目标区域的和。
完整的C++实现代码
下面的代码实现了二维前缀和的构建和区域和查询功能，包含完整的示例：
#include <iostream>
#include <vector>
using namespace std;
class NumMatrix {
private:
// 前缀和数组，比原矩阵多一行一列
vector<vector<int>> prefix;
public:
// 构造函数，构建二维前缀和数组
NumMatrix(vector<vector<int>>& matrix) {
int m = matrix.size();
if (m == 0) return;
int n = matrix[0].size();
// 初始化前缀和数组，全部元素为0
prefix.resize(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];
}
}
}
// 查询区域和，x1,y1是左上角坐标，x2,y2是右下角坐标，均为0基索引
int sumRegion(int x1, int y1, int x2, int y2) {
// 转换为前缀和数组的索引，需要加1
return prefix[x2+1][y2+1] - prefix[x1][y2+1] - prefix[x2+1][y1] + prefix[x1][y1];
}
};
int main() {
// 定义测试用的原矩阵
vector<vector<int>> matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
// 构建二维前缀和对象
NumMatrix numMatrix(matrix);
// 查询左上角(0,0)到右下角(1,1)的区域和，预期结果为1+2+4+5=12
cout << "区域(0,0)到(1,1)的和: " << numMatrix.sumRegion(0, 0, 1, 1) << endl;
// 查询左上角(1,1)到右下角(2,2)的区域和，预期结果为5+6+8+9=28
cout << "区域(1,1)到(2,2)的和: " << numMatrix.sumRegion(1, 1, 2, 2) << endl;
// 查询整个矩阵的区域和，预期结果为45
cout << "整个矩阵的和: " << numMatrix.sumRegion(0, 0, 2, 2) << endl;
return 0;
}
算法复杂度分析
二维前缀和的构建过程需要遍历原矩阵的所有元素，因此构建前缀和数组的时间复杂度是O(m*n)，其中m和n分别是原矩阵的行数和列数。
每次区域和查询只需要做四次加减运算，时间复杂度是O(1)，相比暴力查询的O((x2-x1+1)*(y2-y1+1))复杂度，在多次查询的场景下优势非常明显。
空间复杂度方面，我们需要额外存储前缀和数组，大小为O(m*n)，属于可以接受的额外空间开销。
适用场景说明
二维前缀和非常适合需要频繁对同一个矩阵进行不同区域和查询的场景，比如图像处理中的区域像素值统计、二维数组的区间求和问题等。如果只需要进行少数几次查询，那么直接暴力遍历区域元素可能更简单，不需要额外构建前缀和数组。开发者可以根据实际的查询频率来选择是否使用这种优化方案。