class NumMatrix:
function init(matrix):
this.m = matrix.length
this.n = matrix[0].length if this.m > 0 else 0
this.matrix = 2D array of size m x n, filled with 0
this.tree = 2D array of size (m+1) x (n+1), filled with 0
for i = 0 to this.m - 1:
for j = 0 to this.n - 1:
this.update(i, j, matrix[i][j])
function update(row, col, val):
delta = val - this.matrix[row][col]
this.matrix[row][col] = val
i = row + 1
while i <= this.m:
j = col + 1
while j <= this.n:
this.tree[i][j] += delta
j += j & (-j)
i += i & (-i)
function _query(row, col):
result = 0
i = row
while i > 0:
j = col
while j > 0:
result += this.tree[i][j]
j -= j & (-j)
i -= i & (-i)
return result
function sumRegion(r1, c1, r2, c2):
return (this._query(r2+1, c2+1) - this._query(r1, c2+1)
- this._query(r2+1, c1) + this._query(r1, c1))
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
$ curl repovive.com/roadmaps/data-structures/fenwick-trees/2d-bit-solution
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████