Fenwick Tree
In plain terms
A compact structure for prefix sums with fast updates.
Going deeper
A Fenwick (binary indexed) tree computes prefix sums and updates in logarithmic time using a clever bit-based indexing, more space-efficient than a segment tree for sums. It's elegant and fast.
Under the hood
Uses the lowest set bit to navigate; simpler and smaller than segment trees but limited to invertible operations like sums.
Examples
Cumulative frequency, range-sum queries, inversion counting, rankings.
Think of it like...
Like running subtotals kept at clever checkpoints so any prefix total is quick to assemble.