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

Answer many half-open range sums over one unchanged sequence. Query boundaries are positions between elements; [i,i) is valid and has sum zero.

Summing each range independently costs work proportional to all requested lengths. Preprocessing should instead store one cumulative boundary value per position. Omitting the leading zero creates unnecessary special cases at the beginning.

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.

A prefix table stores the sum before each index. For a half-open range, subtracting the prefix at left from the prefix at right cancels exactly the preceding elements. The extra leading zero removes the left=0 special case. Prototype scans each range; final O(n+q) time and O(n) space.

The cancellation identity can be inspected independently of table construction:

import java.util.*;

class Example {
    public static void main(String[] args) {
        long[] prefix = {0, 4, 2, 9}; // boundaries for [4, -2, 7]
        int left = 1, right = 3;
        assert prefix[right] - prefix[left] == 5;
        assert prefix[2] - prefix[2] == 0;
        assert prefix.length == 4;
    }
}

The leading zero represents the empty prefix. Subtracting boundary totals removes exactly the elements before left. Negative input values do not invalidate this identity; monotonicity of totals is not needed. Validation must check every boundary before using it.

When the ledger changes

Prefix aggregates fit repeated analytics queries over immutable snapshots. When updates arrive between queries, the prefix table becomes stale and an update-aware structure such as a Fenwick tree may be appropriate.

Return sums for [left,right) in query order. Negative values and empty ranges are valid; empty sums are zero. Reject any range unless 0 <= left <= right <= values.length, preserving both inputs even when a later query is invalid.

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.

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