# Leetcode: Range Sum Query 2D – Immutable

Range Sum Query 2D – Immutable

Similar Problems:

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).

Range Sum Query 2D
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

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.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

```## Blog link: https://code.dennyzhang.com/range-sum-query-2d-immutable
class NumMatrix(object):
## Idea: Maintain a matrix: value[i][j] = sum(matrix[0][0] to matrix[i][j]).
##       Thus we can get the sum in Time O(1)
## Complexity:
def __init__(self, matrix):
"""
:type matrix: List[List[int]]
"""
self.is_empty = False
if matrix is None:
self.is_empty = True
return
height = len(matrix)
if height == 0:
self.is_empty = True
return

width = len(matrix[0])
self.sum_matrix = []*height
for i in range(0, height):
self.sum_matrix.append([0]*width)
# calculate the sum
for i in range(0, height):
for j in range(0, width):
if i == 0:
self.sum_matrix[i][j] = 0
for k in range(0, j+1):
self.sum_matrix[i][j] += matrix[i][k]
elif j == 0:
self.sum_matrix[i][j] = 0
for k in range(0, i+1):
self.sum_matrix[i][j] += matrix[k][j]
else:
self.sum_matrix[i][j] = matrix[i][j] \
+ self.sum_matrix[i-1][j] \
+ self.sum_matrix[i][j-1] \
- self.sum_matrix[i-1][j-1]

def sumRegion(self, row1, col1, row2, col2):
"""
:type row1: int
:type col1: int
:type row2: int
:type col2: int
:rtype: int
"""
if self.is_empty:
return None
else:
return self.sum_matrix[row2][col2] \
- (self.sum_matrix[row1-1][col2] if row1>0 else 0) \
- (self.sum_matrix[row2][col1-1] if col1>0 else 0) \
+ (self.sum_matrix[row1-1][col1-1] if row1>0 and col1>0 else 0)

# Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix(matrix)
# param_1 = obj.sumRegion(row1,col1,row2,col2)
```

Share It, If You Like It.