Range Sum Query 2D - Immutable

[huimeich]

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

[huimeich]

def __init__(self, matrix: List[List[int]]):
    if not matrix: return 
    self.sum = [[0 for i in range(len(matrix[0]) + 1)] for j in range(len(matrix) + 1)]
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            self.sum[i+1][j+1] = matrix[i][j] + self.sum[i][j+1] + self.sum[i+1][j] - self.sum[i][j]
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
    return self.sum[row2+1][col2+1] - self.sum[row2+1][col1] -self.sum[row1][col2+1] + self.sum[row1][col1]