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

Use half-open ranges [left, right): include left and exclude right. Their length is right-left, adjacent ranges do not double-count a shared endpoint, and [i, i) is empty.

Subtracting two saved boundaries

Define prefix[i] as the sum of values strictly before i. There are n+1 boundaries for n values, starting with zero. For [3, -2, 5, 4], the boundary totals are [0, 3, 1, 6, 10]. A query [1, 4) subtracts 3 from 10, leaving 7. An empty range subtracts a boundary from itself.

The invariant relies on cancellation, not increasing totals, so negative values are valid. Validate endpoints explicitly: JavaScript slice silently clamps some invalid bounds and will not enforce this API's contract. Also, a chained mathematical comparison such as 0 <= left <= right does not mean the same thing in JavaScript; express each comparison and combine booleans with &&.

The initial zero removes special cases for a range starting at zero. Prefix minima do not support the same subtraction trick because minimum has no inverse that removes an earlier contribution.

const prefix = [0, 3, 1, 6, 10];
console.log(prefix[4] - prefix[1]); // 7 for [1, 4)
console.log(prefix[2] - prefix[2]); // 0 for an empty range
const left = 1, right = 4, length = 4;
console.log(0 <= left && left <= right && right <= length); // true

When the ledger changes

Independent range scans cost O(nq) in the worst case. One prefix table yields O(n+q) total time and O(n) auxiliary storage. Use it for static measurements, event counts or repeated report totals. For interleaved point updates, changing an early value invalidates many prefixes; a Fenwick or segment tree can be more appropriate.

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