LeetCode OJ：Range Sum Query 2D

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Example:

Given matrix = [
  [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]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

Note:

1. You may assume that the matrix does not change.
2. There are many calls to sumRegion function.
3. You may assume that row1 ≤ row2 and col1 ≤ col2.

前面一个博文的衍生版本，由原来的一维矩阵变成了现在的二维矩阵，没什么区别，还是先建立和的数组，代码如下所示：

class NumMatrix {
public:
    NumMatrix(vector<vector<int>> &matrix){
        if(!matrix.size() || !matrix[0].size())
            return;
        sum = vector<vector<int>>(matrix.size(), vector<int>(matrix[0].size(), 0));
        for(int i = 0; i < matrix.size(); ++i){
            for(int j = 0; j < matrix[0].size(); ++j){
                if(i != 0 && j != 0){
                    sum[i][j] = matrix[i][j] + sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1];
                }else if(i == 0 && j == 0){
                    sum[i][j] = matrix[i][j];
                }else if(i == 0){
                    sum[i][j] = matrix[i][j] + sum[i][j-1];
                }else{
                    sum[i][j] = matrix[i][j] + sum[i-1][j];
                }
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        if(row1 == 0 && col1 == 0)
            return sum[row2][col2];
        else if(row1 == 0)
            return sum[row2][col2] - sum[row2][col1-1];
        else if(col1 == 0)
            return sum[row2][col2] - sum[row1-1][col2];
        else
            return sum[row2][col2] - sum[row2][col1-1] -  sum[row1-1][col2] + sum[row1-1][col1-1];
        
    }
private:
    vector<vector<int>> sum;
};