Fenwick Tree

Peter Fenwick, 1994

Fenwick’s 1994 structure maintains cumulative frequencies in an implicit tree so prefix sums and point updates both cost O(log n). Gold highlights trace the descending query path using i − lowbit(i); after a toy update at index 3, rose accents show which cells absorb the delta.