Solution
from typing import List
class NumMatrix:
def __init__(self, matrix: List[List[int]]):
m, n = len(matrix), len(matrix[0])
self.s = [[0] * (n + 1) for _ in range(m + 1)]
for i, row in enumerate(matrix):
for j, v in enumerate(row):
self.s[i + 1][j + 1] = (
self.s[i][j + 1] + self.s[i + 1][j] - self.s[i][j] + v
)
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
return (
self.s[row2 + 1][col2 + 1]
- self.s[row2 + 1][col1]
- self.s[row1][col2 + 1]
+ self.s[row1][col1]
)
if __name__ == "__main__":
mat = [
[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]
]
obj = NumMatrix(mat)
print(obj.sumRegion(2,1,4,3)) # 8
print(obj.sumRegion(1,1,2,2)) # 11
print(obj.sumRegion(1,2,2,4)) # 12