class NumMatrix:
def __init__(self, matrix):
self.m = len(matrix)
self.n = len(matrix[0]) if self.m else 0
self.matrix = [[0]*self.n for _ in range(self.m)]
self.tree = [[0]*(self.n+1) for _ in range(self.m+1)]
for i in range(self.m):
for j in range(self.n):
self.update(i, j, matrix[i][j])
def update(self, row, col, val):
delta = val - self.matrix[row][col]
self.matrix[row][col] = val
i = row + 1
while i <= self.m:
j = col + 1
while j <= self.n:
self.tree[i][j] += delta
j += j & (-j)
i += i & (-i)
def _query(self, row, col):
result = 0
i = row
while i > 0:
j = col
while j > 0:
result += self.tree[i][j]
j -= j & (-j)
i -= i & (-i)
return result
def sumRegion(self, r1, c1, r2, c2):
return (self._query(r2+1, c2+1) - self._query(r1, c2+1)
- self._query(r2+1, c1) + self._query(r1, c1))
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
$ curl repovive.com/roadmaps/data-structures/fenwick-trees/2d-bit-solution
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████