Leetcode-304: two dimensional area and retrieval - matrix immutable

subject

Topic linking

Given a two-dimensional matrix matrix, Multiple requests of the following types ：

• Calculate the sum of the elements in its subrectangle , Of the submatrix top left corner by (row1, col1) , The lower right corner by (row2, col2) .

Realization NumMatrix class ：

• NumMatrix(int[][] matrix) Given an integer matrix matrix To initialize
• int sumRegion(int row1, int col1, int row2, int col2) return top left corner (row1, col1) 、 The lower right corner (row2, col2) The elements of the described submatrix The sum of the .

Example 1：

 Input : 
["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]]
 Output : 
[null, 8, 11, 12]

 explain :
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 ( The sum of the elements of the red rectangle )
numMatrix.sumRegion(1, 1, 2, 2); // return 11 ( The sum of the elements of the green rectangle )
numMatrix.sumRegion(1, 2, 2, 4); // return 12 ( Sum of elements in blue rectangle )

Problem solving

Method 1 ： The prefix and

preSums[i][j] The upper left corner is (0,0), The index in the lower right corner is (i,j) All elements in the matrix of and

1、 First, calculate preSums[i][j]
$S(O,D)=S(O,C)+S(O,B)-S(O,A)+D$

2、 According to the calculated preSums, You can get the sum of all the elements in the matrix you want to calculate
$S(A,D)=S(O,D)-S(O,E)-S(O,F)+S(O,G)$

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