To compute prefix sum from to :
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.