Iterative Query and Update

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: $O(\log n)$ for both. Space: $O(n)$.