leetcode：304. 2D area and retrieval - matrix immutable

Title source

• leetcode：304. Two dimensional region and retrieval - The matrix is immutable

Title Description

class NumMatrix {
    
public:
    NumMatrix(vector<vector<int>>& matrix) {
    

    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
    

    }
};

title

This problem requires finding the sum of submatrixes

violence

class NumMatrix {
    
    vector<vector<int>> mt;
public:
    NumMatrix(vector<vector<int>>& matrix) {
    
        this->mt = matrix;
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
    
        int sum = 0;
        for (int i = row1; i <= row2; ++i) {
    
            for (int j = col1; j <= col2; ++j) {
    
                sum += mt[i][j];
            }
        }
        return sum;
    }
};

One dimensional prefixes and

We can think of two-dimensional arrays as multiple one-dimensional arrays , And find the prefix sum of all one-dimensional data , Then calculate the sum of the matrix

class NumMatrix {
    
    vector<vector<int>> preSum;
public:
    NumMatrix(vector<vector<int>>& matrix) {
    
        int m = matrix.size();  // Take the number of lines 
        if(m > 0){
    
            int n = matrix[0].size(); // Take the number of columns 
            preSum.resize(m, std::vector<int>(n + 1)); // Create a new one   One more than before 0 A binary array of columns 
            for (int i = 0; i < m; ++i) {
    
                for (int j = 0; j < n; ++j) {
    
                    preSum[i][j + 1] = preSum[i][j] + matrix[i][j];
                }
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
    
        int sum = 0;
        // Add up each line 
        for (int i = row1; i <= row2; ++i) {
    
            sum += preSum[i][col2 + 1] - preSum[i][col1];
        }
        return sum;
    }
};

Two dimensional prefixes and

The so-called two-dimensional prefix and , That is to say (i,j) As the lower right corner ,(0,0) As the sum of a rectangle in the upper left corner


So how do we calculate preSum(i,j) The value of ？

therefore ：preSum(i,j) = preSum(i - 1,j) + preSum(i,j - 1) - preSum(i - 1,j - 1) + matrix(i,j)
With the prefix and we can calculate the value of the middle rectangle

therefore ：result = preSum(row2 + 1,col2 + 1) - preSum(row1,col2 + 1) - preSum(row2 + 1,col1) + preSum(row1,col1);

class NumMatrix {
    
    vector<vector<int>> preSum;
public:
    NumMatrix(vector<vector<int>>& matrix) {
    
        if(!matrix.empty() || !matrix[0].empty()){
    
            return;
        }
        int m = matrix.size(), n = matrix[0].size();
        preSum.resize(m + 1, std::vector<int>(n + 1, 0));
        for (int i = 1; i <= m; ++i) {
    
            for (int j = 1; j < n; ++j) {
    
                //  Calculate each matrix  [0, 0, i, j]  Elements and 
                preSum[i][j] = 
                        preSum[i-1][j] + preSum[i][j-1] + 
                        matrix[i - 1][j - 1] - preSum[i-1][j-1];
            }
        }
    }
    //  Calculate the submatrix  [x1, y1, x2, y2]  Elements and 
    int sumRegion(int row1, int col1, int row2, int col2) {
    
        //  The sum of the target matrix is obtained by the operation of four adjacent matrices 
        return preSum[row2 + 1][col2 + 1] - preSum[row2 + 1][col1] - preSum[row1][col2 + 1] + preSum[row1][col1];
    }
};