2021-12-11 leeched 动态规划 304.二维区域和检索-矩阵不可变 c++

2021-12-11 leeched 动态规划 304.二维区域和检索-矩阵不可变 c++ 题目

leetcode.304.二维区域和检索-矩阵不可变

解释
（一）初始化：求矩阵每个元素对应的前缀和
如图所示，对于矩阵中一元素(i, j)，其前缀和为以该元素为右下角的矩形区域内所有值的和，即虚线框内的所有元素值之和

（二）求(r1, c1)-(r2,c2)矩形区域内所有值的和
如图所示， (r1, c1)-(r2,c2)矩形区域内所有值的和 = 虚线框内所有值之和

思路 求矩形前缀和

构造vector presum(m + 1, vector(n + 1, 0)) (m,n分别为matrix的长和宽）
更大的范围是更利于计算presum，因此matrix中的元素在presum中需要扩大。
presum[i][j]:表示的是以matrix[i - 1][j - 1]为右下角的矩形区域的所有值的和，即martrix[i-1][j-1]的矩形前缀和

对于matrix[I][j],求presum[i+1][j+1]:
如下图所示，presum[i+1][j+1] = 红色矩形区域值 + 绿色矩形区域值 - 黑色虚线框矩形区域值 + matrix[i][j]

求(r1, c1)-(r2,c2)矩形区域内所有值的和

如图所示，所求矩形区域值（黄框） = 黑色虚线框值 - 红框 - 绿框 + 灰框
即 presum[r2+1][c2+1]

AC代码

class NumMatrix {
public:
    vector> presum;
    NumMatrix(vector>& matrix) {
        if(matrix.empty())
            return ;
        int m = matrix.size(), n = matrix[0].size();
        presum.resize(m + 1);
        for(int i = 0; i < m + 1; i++)
            presum[i].resize(n + 1);
        for(int i = 1; i < m + 1; i++)
            for(int j = 1; j < n + 1; j++)
                presum[i][j] = presum[i - 1][j] + presum[i][j - 1] - presum[i - 1][j - 1] + matrix[i - 1][j - 1];
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return presum[row2 + 1][col2 + 1] - presum[row2 + 1][col1] - presum[row1][col2 + 1] + presum[row1][col1];
    }
};