Binary indexed tree python code, easy and straightforward

  • 0
    class Bit(object):
        def __init__(self,input):
            n = len(input)
            self.tree = [0 for i in range(n+1)]#start from 1, zero is not used
            for i in range(n):
        def next(self,index):
            return index+(-index&(index))
        def prev(self,index):
            return index-(-index&(index))
        def update(self,index, val):
            next = index
            while next<len(self.tree):
                self.tree[next] += val
                next =
        def sum(self,index):
            prev = index
            res = 0
            while prev>0:
                prev = self.prev(prev)
            return res
        def range_sum(self,l,r):
            if l==0:
                return self.sum(r)
            return self.sum(r) - self.sum(l-1)
    class NumMatrix(object):
        def __init__(self, matrix):
            n = len(matrix)
            self.matrix = matrix
            self.bits = [Bit(matrix[i]) for i in range(n)]
        def update(self, row, col, val):
            bit = self.bits[row]
            prev = self.matrix[row][col]
            self.matrix[row][col] = val
        def sumRegion(self, row1, col1, row2, col2):
            res = 0
            for i in range(row1,row2+1):
                bit = self.bits[i]
                res += bit.range_sum(col1,col2)
            return res

Log in to reply

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