Update goes bottom-up:
def update(self, idx, val):
idx += self.n # leaf position
self.tree[idx] = val
while idx > 1:
idx //= 2
self.tree[idx] = self.tree[2*idx] + self.tree[2*idx+1]
Query processes from leaves upward:
def query(self, l, r):
result = 0
l += self.n
r += self.n + 1
while l < r:
if l & 1:
result += self.tree[l]
l += 1
if r & 1:
r -= 1
result += self.tree[r]
l //= 2
r //= 2
return result
The query processes the range by including nodes on the boundaries and moving toward the root.
Time: for both. Space: .