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 maintains range sums while point values change. Static prefix sums answer queries quickly but an early update invalidates many prefixes. A plain array updates one point quickly but rescans long query ranges. Fenwick blocks balance both operations at logarithmic time.

Public indices are zero based; internal indices begin at one. Internal cell i summarizes the block ending there whose length is its lowest set bit.

Visiting the blocks affected by an addition

For values [2, 1, 4, 3, 5, 2], internal cell 2 covers the first two values and stores 3, cell 4 covers the first four and stores 10, and cell 6 covers the last two and stores 7. Querying prefix length 6 visits cells 6 then 4, yielding 17 from disjoint blocks.

Point additions move upward by adding lowbit; prefix queries move downward by subtracting it. Updating public index 1 starts internally at 2, then visits 4. Internal zero has lowbit zero and would never advance in an update loop. A range [left, right) is prefix(right)-prefix(left), so empty ranges naturally sum to zero.

JavaScript bitwise operators coerce to signed 32-bit integers. This lesson bounds array lengths below 2^31 so internal low-bit indices stay in their valid positive range; stored values and sums remain ordinary safe-integer Numbers and must not be bitwise-coerced. Add means increment, not replacement. Copy initial values into private state and preserve command records.

const internalIndex = 6;
console.log(internalIndex & -internalIndex); // 2: lowest set bit
const cells = [0, 2, 3, 4, 10, 5, 7];
console.log(cells[6] + cells[4]); // 17: disjoint prefix blocks

Keeping additions separate from replacements

A copied-array prototype has O(1) updates and O(n) worst-case sum queries. Fenwick operations touch O(log(n+1)) cells and use O(n) storage. Repeated-add construction costs O(n log(n+1)); dedicated construction can be O(n). Use it for mutable totals and frequencies. Minimum cannot be recovered by subtracting prefixes; a segment tree supports that aggregate.

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