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

A direct query visits exactly the requested positions:

values = [3, -2, 5, 4]
left, right = 1, 4
total = 0
for index in range(left, right):
    total += values[index]
print(total)

The result is 7. Repeating this loop for overlapping ranges repeats the additions.

The prerequisite is a clear interval convention. A half-open range [left, right) includes left and excludes right, just like a Python slice. Its length is right-left; [2, 2) is empty. Half-open intervals let adjacent ranges meet without sharing an element.

Subtracting two saved boundaries

Define prefix[i] as the sum of values strictly before index i. There are n+1 boundaries for n values, so the table begins with zero.

Build the boundary table once, then answer two queries without slicing:

values = [3, -2, 5, 4]
prefix = [0]
for value in values:
    prefix.append(prefix[-1] + value)
print(prefix)
print(prefix[4] - prefix[1], prefix[2] - prefix[2])

The outputs are [0, 3, 1, 6, 10] and 7 0. The extra leading zero handles both empty and start-at-zero ranges uniformly.

For [3, -2, 5, 4]:

To find the sum of [1, 4), take 10 - 3 = 7. Both prefixes include the first value, so subtraction removes it. For [2, 2), subtraction yields 1 - 1 = 0 without a special scan. Negative values do not break this argument: it depends on cancellation, not on totals increasing.

When the ledger changes

For q queries on n values, independent scans cost O(nq) in the worst case. Preprocessing costs O(n) time and space, then each query costs O(1), giving O(n+q) total time. Slicing before summing can additionally allocate a temporary list; a direct range loop avoids that allocation but still performs the repeated additions.

Typical uses include time-series totals, per-day activity reports, and counting occurrences inside intervals after encoding an event as 1 or 0. The same idea works for XOR because a prefix contribution can be undone. It does not let you subtract two prefix minima: knowing the minimum of two prefixes does not identify the minimum of their difference.

Use a scan when there are few short queries and preprocessing would cost more than it saves. Use a Fenwick or segment tree when updates and queries are interleaved; changing an early element invalidates many static prefix totals. Validate bounds explicitly, because Python slices silently accept some out-of-range indices that this API rejects.

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