1. Firstly, I try to solve this in a naive way: (1) use an array, and scan from i to j when sum or (2) use an accumulating array to store the sum so far. TLE of course, you know O(n)+O(1) or O(1)+n(n)...

2. Then i tried segment tree (for the first time), it works~ looks like this:

``````class SegmentTreeNode(object):
def __init__(self, val=None, left_node=None, right_node=None, left_bound=None, right_bound=None):
self.val = val
self.left_node = left_node
self.right_node = right_node
self.left_bound = left_bound
self.right_bound = right_bound

class NumArray(object):
def construct_segment_tree(self, nums, l, r):
#1. exit
if l==r-1:
leave_node = SegmentTreeNode(nums[l], None, None, l, r)
return leave_node
#2. general
mid = (l+r)/2
right_subtree = self.construct_segment_tree(nums, mid, r)
left_subtree = self.construct_segment_tree(nums, l, mid)
root = SegmentTreeNode(right_subtree.val+left_subtree.val, left_subtree, right_subtree, l, r)
return root

def __init__(self, nums):
if len(nums)==0:
self.segment_tree_root = None
return
self.segment_tree_root = self.construct_segment_tree(nums, 0, len(nums))

def update_core(self, root, i, val):
#1. exit
if root.left_bound==root.right_bound-1:
diff = val-root.val
root.val += diff
return diff

#2. general
mid = (root.left_bound+root.right_bound)/2
if i<mid:
diff = self.update_core(root.left_node, i, val)
else:
diff = self.update_core(root.right_node, i, val)
root.val += diff
return diff

def update(self, i, val):
self.update_core(self.segment_tree_root, i, val)

def sumRange_core(self, root, i, j):
#1.exit
if root==None or j<=root.left_bound or i>=root.right_bound:
return 0
#if i==root.left_bound and j==root.right_bound:
if i<=root.left_bound and root.right_bound<=j:
return root.val

#2. general
return self.sumRange_core(root.left_node, i, j)+self.sumRange_core(root.right_node, i, j)

def sumRange(self, i, j):
return self.sumRange_core(self.segment_tree_root, i, j+1)
``````

Not elegant enough and the time is about 600ms...

1. So i tried Binary Indexed Tree, and got 148ms, as following:
``````class NumArray(object):
def __init__(self, nums):
self.n = len(nums)
self.a, self.c = nums, [0] * (self.n + 1)
for i in range(self.n):
k = i + 1
while k <= self.n:
self.c[k] += nums[i]
k += (k & -k)

def update(self, i, val):
diff, self.a[i] = val - self.a[i], val
i += 1
while i <= self.n:
self.c[i] += diff
i += (i & -i)

def sumRange(self, i, j):
res, j = 0, j + 1
while j:
res += self.c[j]
j -= (j & -j)
while i:
res -= self.c[i]
i -= (i & -i)
return res
``````

Note: It is same with segment tree logically, but more elegant and concise and FAST~!

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