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

Process point additions and range-sum queries on internal state without mutating the caller array. A one-time prefix table becomes stale as soon as the first update is applied.

Copy-and-scan is a good correctness baseline but long ranges remain linear per query. Fenwick nodes summarize binary-sized blocks so both point additions and prefix sums visit logarithmically many nodes.

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.

A Fenwick node summarizes a block whose size is its lowest set bit. Prefix queries clear that bit; point additions advance by that bit. Translate zero-based input indices to one-based internal storage to avoid a zero-step loop. Range sums subtract two prefixes. Final O(n log n) simple construction and O(log n) operations, O(n) space; linear construction is optional.

The lowest set bit describes a node block length; one-based storage avoids a zero-step update:

import java.util.*;

class Example {
    public static void main(String[] args) {
        int index = 12; // binary 1100
        int blockLength = index & -index;
        assert blockLength == 4;
        assert index - blockLength == 8;
        assert (0 & -0) == 0;
    }
}

A prefix query can jump to the preceding block by subtracting this value. An update uses the corresponding forward jumps. Starting that update at index zero would never advance; translate zero-based public indices deliberately.

Keeping additions separate from replacements

Fenwick trees suit running counts, cumulative totals, and frequency tables with point increments. They trade a compact specialized representation for less flexibility than a general segment tree.

Update("add", index, delta) changes internal state; Update("sum", left, right) queries [left,right). Return only query totals in order. Negative values/deltas and empty ranges are valid. Reject unknown operations, out-of-bounds add indices, and ranges unless 0 <= left <= right <= n. Preserve original values and commands.

Numeric arithmetic uses long; indices use int. Inputs follow the declared types and contain no null elements unless the API permits them. Preserve caller-owned collections, including on failure, and use IllegalArgumentException for the documented invalid arguments.

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