Bits Segment Tree


  • 0
    Z
    from math import log, ceil
    
    class NumArray(object):
    
        def __init__(self, nums):
            """
            :type nums: List[int]
            """
            if not nums:
                return
            length = len(nums)
            self.tree = [0] * (1 << int(ceil(log(length, 2)) + 1))
            self.leaf = len(self.tree) >> 1
            self.tree[self.leaf: self.leaf + length] = nums
            self.build()
            print self.tree
            
        def build(self):
            for i in xrange(self.leaf - 1, 0, -1):
                self.tree[i] = sum([self.tree[i << 1], self.tree[(i << 1) + 1]])
    
        def update(self, i, val):
            """
            :type i: int
            :type val: int
            :rtype: void
            """
            idx = self.leaf + i
            self.tree[idx] = val
            while idx > 0:
                idx >>= 1
                self.tree[idx] = sum([self.tree[idx << 1], self.tree[(idx << 1) + 1]])
    
        def sumRange(self, i, j):
            """
            :type i: int
            :type j: int
            :rtype: int
            """
            s = self.leaf + i - 1
            e = self.leaf + j + 1
            total = 0
            while s ^ e != 1:
                if ~s & 1:
                    total += self.tree[s ^ 1]
                if e & 1:
                    total += self.tree[e ^ 1]
                s >>= 1
                e >>= 1
            return total
    

Log in to reply
 

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