Share 2 solutions in Python: 'Bit Index Tree' and 'ZKW Segment Tree'


  • 0

    Bit Index Tree (200ms):

    class NumArray(object):
    	def __init__(self, nums):
    		len_nums = len(nums) + 1
    		self.num_array = [0] + nums
    		self.bit_tree = [0] * len_nums
    		for i in xrange(1, len_nums):
    			self.bit_tree[i] = self.sumBefore(i - 1) - self.sumBefore(i - (i&(-i))) + self.num_array[i]
    
    
    	def sumBefore(self, i):
    		return 0 if i == 0 else self.bit_tree[i] + self.sumBefore(i - (i&(-i)))
    
    
    	def update(self, i, val):
    		i += 1
    		diff = val - self.num_array[i] 
    		self.num_array[i] += diff
    		len_nums = len(self.num_array)
    		while (i < len_nums):
    			self.bit_tree[i] += diff
    			i += (i&(-i))
    
    	def sumRange(self, i, j):
    		return self.sumBefore(j + 1) - self.sumBefore(i)
    

    ZKW Segment Tree (180 ms):

    class NumArray1(object):
    	def log2(self, num):
    		ret = 0
    		while num != 0:
    			num >>= 1
    			ret += 1
    		return ret
    
    	def __init__(self, nums):
    		len_nums = len(nums)
    		self.idx_shift = 2 ** (self.log2(len_nums))
    		self.num_array = [0] * (self.idx_shift) + nums + [0] * (self.idx_shift - len_nums)
    		for i in xrange(self.idx_shift - 1, 0, -1):
    			self.num_array[i] = self.num_array[i << 1] + self.num_array[(i << 1) + 1]
    
    	def update(self, i, val):
    		i += self.idx_shift
    		diff = val - self.num_array[i] 
    		while i > 0:
    			self.num_array[i] += diff
    			i >>= 1
    
    	def sumRange(self, i, j):
    		result = 0
    		i += self.idx_shift
    		j += self.idx_shift
    		if i == j:
    			return self.num_array[i]
    		while i^j != 1:
    			result -= self.num_array[i - 1] if i & 1 == 1 else 0
    			result -= self.num_array[j + 1] if j & 1 == 0 else 0
    			i >>= 1
    			j >>= 1
    		result += self.num_array[i] + self.num_array[j]
    		return result

Log in to reply
 

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