Given array:
[3, 0, 1],
[5, 6, 3],
[1, 2, 0]
Firstly, let's calculate prefix sums for each row:
matrix[row][col] = matrix[row][col] + matrix[row][col - 1]
=>
[3, 3, 4],
[5, 11, 14],
[1, 3, 3],
Secondly, let's calculate sums for each region:
matrix[row][col] = matrix[row][col] + matrix[row - 1][col]
=>
[3, 3, 4],
[8, 14, 18],
[9, 17, 21],
Let's calculate sum for region row1=1, col1=1, row2=2, col2=2
Take sum of the region matrix[2][2] -> 21
Substract the sum of region matrix[0][2] -> 4
Substract the sum of region matrix[2][0] -> 9
But we've substracted twice the sum of matrix[0][0]
So we have to add matrix[0][0] to answer
So anwer will be:
sumRegion(1,1,2,2) -> 21 - 4 - 9 + 3 = 11
class NumMatrix:
def __init__(self, matrix: List[List[int]]):
m, n = len(matrix), len(matrix[0])
self.sum = [[0] * (n + 1) for _ in range(m + 1)] # sum[i][j] is sum of all elements inside the rectangle [0,0,i,j]
for r in range(1, m + 1):
for c in range(1, n + 1):
self.sum[r][c] = self.sum[r - 1][c] + self.sum[r][c - 1] - self.sum[r - 1][c - 1] + matrix[r - 1][c - 1]
def sumRegion(self, r1: int, c1: int, r2: int, c2: int) -> int:
r1, c1, r2, c2 = r1 + 1, c1 + 1, r2 + 1, c2 + 1 # Since our `sum` starts by 1 so we need to increase r1, c1, r2, c2 by 1
return self.sum[r2][c2] - self.sum[r2][c1 - 1] - self.sum[r1 - 1][c2] + self.sum[r1 - 1][c1 - 1]
class NumMatrix:
def __init__(self, matrix: List[List[int]]):
n_rows = len(matrix)
n_cols = len(matrix[0])
# make prefix sums for rows
for r in range(n_rows):
for c in range(1, n_cols):
matrix[r][c] = matrix[r][c] + matrix[r][c-1]
# make prefix sums for regions
for r in range(1, n_rows):
for c in range(n_cols):
matrix[r][c] = matrix[r][c] + matrix[r-1][c]
self.matrix = matrix
def sumRegion(self, r1: int, c1: int, r2: int, c2: int) -> int:
current_region_sum = self.matrix[r2][c2]
top_region_sum = self.matrix[r1-1][c2] if r1 != 0 else 0
left_region_sum = self.matrix[r2][c1-1] if c1 != 0 else 0
origin = self.matrix[r1-1][c1-1] if r1 != 0 and c1 != 0 else 0
return current_region_sum - top_region_sum - left_region_sum + origin
class NumMatrix:
def __init__(self, matrix: List[List[int]]):
if not matrix: return
m, n = len(matrix), len(matrix[0])
dp = self.dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m):
for j in range(n):
dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] + matrix[i][j] - dp[i][j]
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
dp = self.dp
return dp[row2+1][col2+1] - dp[row2+1][col1] - dp[row1][col2+1] + dp[row1][col1]