Module fenwick 

Fenwick tree (Binary Indexed Tree) for O(log n) prefix sum queries. Cache-friendly Fenwick tree (Binary Indexed Tree) for prefix sums.

Provides O(log n) point update and prefix query over a contiguous Vec<u32>, with a batch update API that amortises multiple deltas into a single pass.

Layout

The tree is stored 1-indexed in a contiguous Vec<u32> of length n + 1 (index 0 unused). This gives cache-friendly sequential access and avoids indirection. For a typical 100k-item list with u32 heights, the tree occupies ~400 KB — well within L2 cache on modern CPUs.

Operations

Operation	Time	Allocations
new(n)	O(n)	1 Vec
update(i, delta)	O(log n)	0
prefix(i)	O(log n)	0
range(l, r)	O(log n)	0
batch_update(deltas)	O(m log n)	0
rebuild(values)	O(n)	0
find_prefix(target)	O(log n)	0

Invariants

1. tree[i] stores the sum of elements in a range determined by lowbit(i).
2. prefix(n) == sum of all values.
3. After rebuild, the tree exactly represents the given values.
4. batch_update produces identical results to sequential update calls.

Structs

FenwickTree

Fenwick tree (Binary Indexed Tree) for prefix sum queries over u32 values.