题目

给定一个二维矩阵 matrix，以下类型的多个请求：

计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。

实现 NumMatrix 类：

NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素总和。

示例：
[中等] 304. 二维区域和检索 - 矩阵不可变 - 图1

输入: 
["NumMatrix","sumRegion","sumRegion","sumRegion"]
[[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出: 
[null, 8, 11, 12]
解释:
NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)

解答 & 代码

求区间和的二维版本，仍是用前缀和的方法解题。

初始化求前缀和矩阵：

前缀和矩阵：prefixSum[row][col] 代表以 [0, 0] 为左上角、[row-1, col-1] 为右下角的矩阵内的元素和。因此，prefixSum[row][col] = matrix[row - 1][col - 1] + prefixSum[row - 1][col] + prefixSum[row][col - 1] - prefixSum[row - 1][col - 1]

eg. 如下图所示，prefixSum[3][4] = 红色矩形内元素和 = 黑色方格值 + 蓝色矩形内元素和 + 绿色矩形内元素和 - 蓝、绿重叠的咖色矩形内元素和

检索求矩阵内元素和

以 [row1, col1] 为左上角、[row2, col2] 为右下角的矩阵内的元素和 = prefixSum[row2 + 1][col2 + 1] - prefixSum[row1][col2 + 1] - prefixSum[row2 + 1][col1] + prefixSum[row1][col1]

eg. 如下图所示，红色矩形（[2, 1, 3, 3）内的元素和 = 黑色矩形前缀和 - 蓝色矩形前缀和 - 绿色矩形的前缀和+ 蓝、绿重叠的咖色矩形的前缀和

class NumMatrix {
private:
    // 前缀和矩阵，
    // prefixSum[row][col] 代表以 [0, 0] 为左上角、[row-1, col-1] 为右下角的矩阵内的元素和
    vector<vector<int>> prefixSum;
public:
    // 初始化：构造前缀和矩阵
    NumMatrix(vector<vector<int>>& matrix) {
        if(matrix.size() == 0 || matrix[0].size() == 0)
            return;
        int rows = matrix.size();
        int cols = matrix[0].size();

        // 注意二维 vector resize 的方法
        prefixSum.resize(rows + 1, vector<int>(cols + 1, 0));   // resize，并初始化为 0
        for(int row = 1; row <= rows; ++row)
        {
            for(int col = 1; col <= cols; ++col)
            {
                prefixSum[row][col] = matrix[row - 1][col - 1] + prefixSum[row - 1][col] +
                                        prefixSum[row][col - 1] - prefixSum[row - 1][col - 1];
            }
        }
    }

    // 计算以 [row1, col1] 为左上角、[row2, col2] 为右下角的矩阵内的元素和
    int sumRegion(int row1, int col1, int row2, int col2) {
        return prefixSum[row2 + 1][col2 + 1] - prefixSum[row1][col2 + 1] - 
                prefixSum[row2 + 1][col1] + prefixSum[row1][col1];
    }
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
 */

复杂度分析：设传入的二维矩阵 M 行 N 列

时间复杂度：初始化的时间复杂度 O(MN)，每次检索的时间复杂度 O(1)
空间复杂度 O(MN)

执行结果：

执行结果：通过

执行用时：368 ms, 在所有 C++ 提交中击败了 49.88% 的用户
内存消耗：144.5 MB, 在所有 C++ 提交中击败了 58.76% 的用户