Fenwick trees

An event dashboard reports registration totals over date ranges. Cancellations and late registrations keep adjusting individual days while people query the report. Static prefix sums make reads cheap, but one correction near the beginning invalidates many saved totals.

A Fenwick tree stores overlapping sum blocks so both a point addition and a prefix query touch only logarithmically many cells. A range total still comes from subtracting two prefixes.

Correcting daily counts between reports

A Fenwick tree stores sums of binary-sized blocks. Public indices remain zero based, while internal index i stores a block ending at i whose length is its lowest set bit. Prefix reads repeatedly remove that bit; point additions repeatedly add it.

Visiting the blocks affected by an addition

For [2, 1, 4, 3, 5, 2], the first six values sum to seventeen. Adding three at public index one updates internal cells two and four; querying the six-value prefix reads cells six and four and returns twenty. i & -i identifies the block step. Convert to one-based indices before updating, because a step from internal zero never advances.

std::size_t i=12;
auto block=i & (~i+1); // 4 for unsigned 12

Keeping additions separate from replacements

Using internal index zero for an update would never advance because its low bit is zero. Convert a validated public index to index+1. A range total is the difference of two prefix totals, so empty ranges naturally return zero. Unlike a static prefix table, a point update touches only O(log n) blocks. Negative deltas do not affect the structure's correctness. Keep tree state local to each invocation: a later call must not inherit earlier updates. Validate commands and ranges without modifying either caller-owned input vector.

A point addition or prefix query visits O(log(n+1)) blocks; the tree uses O(n) space. Building by repeated additions costs O(n log(n+1)), though a dedicated build can be linear. Negative deltas are valid because sums can be subtracted. Prefix minima do not have the same inverse.

Use the supplied Int, Vec, and Opt aliases. Numeric arithmetic fits signed long long; absence uses std::nullopt, and documented invalid inputs throw std::invalid_argument. Keep caller-owned containers unchanged.

A cancellation is a delta to a daily count, so adding a value and replacing it must not be confused.