The problem
Design a structure over an integer array supporting update(index, val) and sumRange(left, right), both called many times.
Stuck? Reveal hints one at a time
How to approach it
- 1Build a Fenwick tree: tree[i] covers a block of size lowbit(i) ending at i (1-indexed).
- 2add(i, delta): while i ≤ n, tree[i] += delta, i += i & (−i).
- 3prefix(i): while i > 0, total += tree[i], i −= i & (−i).
- 4update = add(index, newVal − old[index]); sumRange(l, r) = prefix(r+1) − prefix(l).
Key insight
i & (−i) isolates the lowest set bit — climbing by adding/removing it visits exactly the O(log n) blocks that cover any prefix.
The solution
Watch out for
- update receives the NEW value, but the tree needs the DELTA — keep a copy of current values.
- Fenwick trees are 1-indexed internally; off-by-one at the boundary is the classic bug.