Updatable prefix sums
A plain prefix sum array answers range sum queries instantly but breaks the moment a value changes, since every later prefix must be rebuilt. A binary indexed tree, also called a Fenwick tree, supports both point updates and prefix sum queries quickly by storing partial sums cleverly along powers of two.
How the indexing works
Each tree position is responsible for a block of original elements whose length equals the lowest set bit of that index. To query a prefix you jump backward, clearing the lowest set bit each step and accumulating partial sums. To update you jump forward, adding the lowest set bit each step, touching every block that covers the changed position. Both walks visit only a logarithmic number of positions.
What it is used for
- Running counts and sums that change over time.
- Counting inversions in an array by sweeping and querying how many larger elements appeared earlier.
- Range update and range query variants built from two trees.
- Order statistics when values are mapped to compact indices.
Key idea
Store partial sums keyed by the lowest set bit so both updates and prefix queries walk a logarithmic path, enabling dynamic counts, inversion counting, and order statistics.