To add to position , update all positions that include in their range:
def update(i, delta):
while i <= n:
tree[i] += delta
i += lowbit(i)
``` Example: update position $3$:
- Update `tree[3]` (covers element 3)
- $3 + \text{lowbit}(3) = 3 + 1 = 4$
- Update `tree[4]` (covers elements 1-4, includes 3)
- $4 + \text{lowbit}(4) = 4 + 4 = 8$
- Update `tree[8]` (covers elements 1-8, includes 3)
- Continue until exceeding $n$ Each position's responsibility range either includes $i$ entirely or not at all.
You update exactly those that include it. Time: $O(\log n)$ iterations.