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

• 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``````

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