Range Sum Query 2D – Immutable

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by (row1, col1), (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.

Dynamic programming.

dp[i][j] stores the sum of elements in the rectangle area between(0,0) and (i,j)

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

    int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        // index boundary check
        if(row1 == 0 && col1 == 0) sum = (int)dp[row2][col2];
        else if(row1 == 0){
            sum = (int)(dp[row2][col2] - dp[row2][col1 - 1]);
        }else if(col1 == 0){
            sum = (int)(dp[row2][col2] - dp[row1 - 1][col2]);
        }else{
            sum = (int)(dp[row2][col2] + dp[row1 - 1][col1 - 1] - dp[row2][col1 - 1] - dp[row1 - 1][col2]);
        }
        return sum;
    }
};


// Your NumMatrix object will be instantiated and called as such:
// NumMatrix numMatrix(matrix);
// numMatrix.sumRegion(0, 1, 2, 3);
// numMatrix.sumRegion(1, 2, 3, 4);