Interactive application
Interactive
Overview · selected highlights
Fenwick trees
A Fenwick tree explained through the ranges it stores. Follow prefix queries and updates through an array, then extend the bookkeeping to range operations and two dimensions, with intermediate state showing why each jump is useful.
UpdatePartitionSum
- [ ]
Partition the range
Each array entry stores a particular aligned interval.
- Σ
Gather a prefix
Combine disjoint stored intervals to answer a cumulative query.
- +
Propagate an update
Visit the entries whose represented intervals contain the change.
- ▦
Extend the structure
Inspect range-update bookkeeping and the two-dimensional construction.
The bit operation is a compact encoding of visible interval structure.
