# [leetcode] Range Sum Query 2D – Immutable

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);```

This site uses Akismet to reduce spam. Learn how your comment data is processed.