Fenwick tree

A Fenwick tree stores a changing array so that a point update and a prefix sum query each take $O(\log n)$ time with $O(n)$ storage. With indices starting at $1$, the entry at $i$ stores the sum over the final block of length $i\&(-i)$ ending at $i$. A query repeatedly removes that final block, while an update visits the blocks containing the changed position.