Binary indexed tree python code, easy and straightforward


  • 0
    Z
    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):
                self.update(i,input[i])
        def next(self,index):
            return index+(-index&(index))
        def prev(self,index):
            return index-(-index&(index))
        def update(self,index, val):
            index+=1
            next = index
            while next<len(self.tree):
                self.tree[next] += val
                next = self.next(next)
        def sum(self,index):
            index+=1
            prev = index
            res = 0
            while prev>0:
                res+=self.tree[prev]
                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
            
            bit.update(col,val-prev)
            
    
        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.