# Python BIT Solution

• ``````def __init__(self, matrix):
"""
:type matrix: List[List[int]]
"""
if len(matrix) == 0 or len(matrix[0]) == 0: return
self.matrix = [[0] * (len(matrix[0])+1)] + [([0] + matrix[i]) for i in range(len(matrix))]
self.tree = [[0 for _ in range(len(self.matrix[0]))] for _ in range(len(self.matrix))]
for i in range(1, len(self.tree)):
for j in range(1, len(self.tree[i])):
lbi, lbj = self._getLowBits(i), self._getLowBits(j)
for ii in range(i-lbi+1, i+1):
for jj in range(j-lbj+1, j+1):
self.tree[i][j] += self.matrix[ii][jj]

def _getLowBits(self, i):
return (-i & i)

def _getPrec(self, i):
return i - self._getLowBits(i)

def _getSucc(self, i):
return i + self._getLowBits(i)

def _getSum(self, row, col):
s = 0
r = row
while r > 0:
c = col
while c > 0:
s += self.tree[r][c]
c = self._getPrec(c)
r = self._getPrec(r)
return s

def update(self, row, col, val):
"""
update the element at matrix[row,col] to val.
:type row: int
:type col: int
:type val: int
:rtype: void
"""
row, col = row+1, col+1
diff = val - self.matrix[row][col]
self.matrix[row][col] = val
r = row
while r < len(self.matrix):
c = col
while c < len(self.matrix[r]):
self.tree[r][c] += diff
c = self._getSucc(c)
r = self._getSucc(r)

def sumRegion(self, row1, col1, row2, col2):
"""
sum of elements matrix[(row1,col1)..(row2,col2)], inclusive.
:type row1: int
:type col1: int
:type row2: int
:type col2: int
:rtype: int
"""
row1, col1, row2, col2 = row1+1, col1+1, row2+1, col2+1
return self._getSum(row2, col2) - self._getSum(row1-1, col2) - \
self._getSum(row2, col1-1) + self._getSum(row1-1, col1-1)``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.