A Fenwick tree (a.k.a. Binary Indexed Tree) stores an array so that prefix sums and point updates both take O(log n). Each BIT cell bit[i] covers the range (i − lowbit(i), i] — the trick is to move by lowbit to walk parents on update and to walk left on query. Load an array, then click any cell to see the exact O(log n) path.
Every positive integer i has a lowest set bit — the value lowbit(i) = i & (-i). That value is both a partition trick and a jump size. Storage cell BIT[i] holds the sum of the last lowbit(i) elements of A, i.e. A[i − lowbit(i) + 1 .. i]. To read the prefix sum up to i, walk i ← i − lowbit(i) until zero, adding each cell along the way. To update A[i], walk i ← i + lowbit(i) up to n, adding the delta to each parent. Because each jump strips or adds one bit, every operation touches at most ⌊log₂ n⌋ + 1 cells. The classic 1994 paper by Peter Fenwick showed this beats a segment tree on memory (n cells vs 4n) with the same asymptotic cost for prefix aggregates — the reason competitive-programming solutions still reach for it constantly.
Reasonable extensions you can imagine on top of this: replace addition with any Abelian group (works: XOR, ⊕ over a field); with min/max you need a companion structure because BIT can't undo an old value; with an implicit inverse you can even support point-update / range-update by holding two BITs.