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. One-based internal index i covers lowbit(i)=i&-i elements. Prefix queries subtract lowbit to move toward zero; additions add lowbit to visit containing blocks.

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.

index := 6
lowbit := index & -index
fmt.Println(lowbit) // 2

Keeping additions separate from replacements

A range sum subtracts two prefixes because addition has an inverse. Negative deltas are valid. Starting at internal zero creates a nonadvancing loop. Static prefixes favor immutable data; a Fenwick tree balances updates and sums at O(log n).

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.

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