Python BIT Solution


  • 0
    Z
    def __init__(self, matrix):
        """
        initialize your data structure here.
        :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)

Log in to reply
 

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