Prefix Sum Query

To compute prefix sum from $1$ to $i$:

def query(i):
    result = 0
    while i > 0:
        result += tree[i]
        i -= lowbit(i)
    return result
``` Example: prefix sum up to index $7$:

- Add `tree[7]` (covers just element 7)
- $7 - \text{lowbit}(7) = 7 - 1 = 6$
- Add `tree[6]` (covers elements 5-6)
- $6 - \text{lowbit}(6) = 6 - 2 = 4$
- Add `tree[4]` (covers elements 1-4)
- $4 - \text{lowbit}(4) = 4 - 4 = 0$
- Stop. You added $tree[7] + tree[6] + tree[4]$, which covers all elements $1$ to $7$.

Time: $O(\log n)$ iterations.