二维数组前缀和板子

注意：初始化矩阵下标从（0,0）开始，而计算子矩阵中元素矩阵和时满足笛卡尔坐标系，从（1,1）开始至右下角坐标，且这两个边界元素都包含！！

#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1005; // 根据需要调整矩阵的最大尺寸
int prefixSum[MAXN][MAXN]; // 存储前缀和的数组

// 初始化前缀和数组
void initPrefixSum(const vector<vector<int>>& matrix) {
    int n = matrix.size();
    int m = matrix[0].size();

    // 初始化前缀和数组为0
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            prefixSum[i][j] = 0;
        }
    }

    // 计算前缀和
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + matrix[i - 1][j - 1];
        }
    }
}

// 获取子矩阵(x1, y1)到(x2, y2)的和（下标从1开始）
int getMatrixSum(int x1, int y1, int x2, int y2) {
    return prefixSum[x2][y2] - prefixSum[x1 - 1][y2] - prefixSum[x2][y1 - 1] + prefixSum[x1 - 1][y1 - 1];
}

int main() {
    // 示例矩阵
    vector<vector<int>> matrix = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };

    // 初始化前缀和
    initPrefixSum(matrix);

    // 获取子矩阵(1, 1)到(2, 2)的和
    int sum = getMatrixSum(1, 1, 2, 2);
    cout << "Sum of submatrix (1, 1) to (2, 2) is: " << sum << endl;

    return 0;
}