Prefix sums

A billing report stores one net usage total per day, including negative adjustments. Finance asks for last week, the first half of the month, and several overlapping campaign periods. Each answer is simple; repeatedly adding the same days is the waste.

The values stay fixed while this report runs. Prefix sums use that pause in updates to prepare one table and turn each later range total into a subtraction.

The report keeps asking for overlapping days

Store totals at boundaries rather than at elements. A vector with n values has n+1 prefix boundaries: prefix[0] is zero and prefix[i] excludes element i. This makes a half-open query [l,r) equal to prefix[r]-prefix[l]; empty ranges subtract a boundary from itself.

Subtracting two saved boundaries

For [3, -2, 5, 4], cumulative totals at the boundaries are [0, 3, 1, 6, 10]. The range [1, 4) is 10 - 3 = 7: both saved totals include day zero, so subtraction removes it. The leading zero handles a range starting at the beginning, and subtracting a boundary from itself gives an empty range's zero total. Negative adjustments don't affect the cancellation argument.

std::vector<Int> prefix{0,4,2,9}; // values {4,-2,7}
Int middle = prefix[3]-prefix[1]; // 5

When the ledger changes

Negative values do not break cancellation. They do break an assumption that prefix sums are sorted, so this table is not automatically a binary-search index. Validate signed indices before converting to size_t; converting -1 first produces a huge unsigned value. operator[] does not check bounds. Build the table once to replace repeated O(n) scans with O(1) queries. Updates to an early element invalidate many boundaries, which is why a Fenwick tree is useful for interleaved updates.

For n values and q queries, independent scans cost O(nq) in the worst case. One O(n) prefix table reduces the total to O(n+q), with O(1) work per query and O(n) auxiliary storage beyond the returned answers. Updates invalidate this static preparation.

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.

Finance can request another interval against the same billing snapshot without scanning those days again.