Leetcode 304. Range Sum Query 2D

Problem reference: https://leetcode.com/problems/range-sum-query-2d-immutable

// My solution
// Calclate all sums of rectangle from {0, 0} to every node.
// The final answer is to subtract some small rectancles
// with raw1,col1 from the larger rectangle with raw2,col2.

class NumMatrix {
public:
    int raw_size, col_size;
    vector<vector<int>> sum;
    NumMatrix(vector<vector<int>> matrix) {
        raw_size = matrix.size();
        col_size = raw_size?matrix[0].size():0;
        
        // Calculate the initial sums.
        for (int i=0; i<raw_size; i++) {
            sum.push_back(vector<int>());
            for (int j=0; j<col_size; j++) {
                sum[i].push_back(matrix[i][j]);
                
                if (j>0) sum[i][j] += sum[i][j-1];
                if (i>0) sum[i][j] += sum[i-1][j];
                
                // If we added a rectangle repeatly, then subtract it.
                if (i>0 && j >0) sum[i][j] -= sum[i-1][j-1];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        int ans = sum[row2][col2];
        if (col1>0) ans -= sum[row2][col1-1];
        if (row1>0) ans -= sum[row1-1][col2];
        
        // If we subtracted a rectangle one more time, then add it back.
        if (col1>0 && row1>0) ans += sum[row1-1][col1-1];
        
        return ans;
    }
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */
原文地址:https://www.cnblogs.com/kkrisen/p/7863097.html