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