collections/fenwick_tree_utils library
Fenwick tree (Binary Indexed Tree) for prefix sums — roadmap #483.
Maintains a mutable array of num and answers prefix-sum and range-sum
queries in O(log n), with O(log n) point updates. A plain array does
either reads OR writes cheaply but not both: a prefix-sum cache makes
queries O(1) but every update O(n), while a raw array makes updates
O(1) but every prefix sum O(n). The Fenwick tree balances both at
O(log n) by storing partial sums over power-of-two-aligned ranges.
The internal tree is 1-based (index 0 is an unused sentinel that lets the
i & -i lowest-set-bit walk terminate), while the public API is 0-based and
inclusive on both ends, so rangeSum(2, 4) sums elements 2, 3, and 4.
Classes
- FenwickTree
-
A Binary Indexed Tree over
numsupporting point updates and range sums.