304. Range Sum Query 2D - Immutable.md

304. Range Sum Query 2D - Immutable

思路

题目要求一个二维区域和的检索，这其实是上一题303. Range Sum Query - Immutable的二维版本， 思路其实也是一样的。

我们建立一个大小和nums一样的区域和数组sum，然后根据边界值的加减法来快速求出给定区域之和。其中sum[i][j]表示累计区间(0, 0)到(i, j)这个矩形区间所有的数字之和， 那么此时如果我们想要快速求出(r1, c1)到(r2, c2)的矩形区间时，只需sum[r2][c2] - sum[r2][c1 - 1] - sum[r1 - 1][c2] + sum[r1 - 1][c1 - 1]即可。 为了避免判断边界值，可以使用一个小技巧，把sum开辟大一点，并令sum[i+1][j+1]表示累计区间(0, 0)到(i, j)这个矩形区间所有的数字之和，见代码。

C++

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