Prefix sums for repeated interval totals

An exclusive prefix sum stores the total before each position. With a leading zero, the sum of the half-open interval [left, right) is always prefix[right] - prefix[left]. For a student answering repeated range queries, this convention removes special cases for intervals starting at zero and gives an empty interval a natural result of zero.

Take values [4, -1, 3, 0, 2]. The prefix array is [0, 4, 3, 6, 6, 8]. Position three stores the total of values at indices zero, one, and two. The prefix array has one more element than the input because it describes every boundary, including the boundary after the final value.

Subtract the shared beginning

The interval from index one through index three inclusive is written [1, 4). The total before boundary four is six; the total before boundary one is four. Subtracting gives two, which matches -1 + 3 + 0.

def prefix_sums(values):
    prefix = [0]
    for value in values:
        prefix.append(prefix[-1] + value)
    return prefix


def range_sum(prefix, left, right):
    if type(left) is not int or type(right) is not int or not 0 <= left <= right < len(prefix):
        raise IndexError('expected 0 <= left <= right <= n')
    return prefix[right] - prefix[left]

prefix = prefix_sums([4, -1, 3, 0, 2])
assert prefix == [0, 4, 3, 6, 6, 8]
assert range_sum(prefix, 1, 4) == 2
assert range_sum(prefix, 2, 2) == 0
assert range_sum(prefix, 0, 5) == 8
assert range_sum(prefix_sums([]), 0, 0) == 0

The bounds check allows right == n because the prefix array has length n + 1. It rejects a reversed interval, negative indices, and endpoints beyond the source. Python’s negative indexing would otherwise silently read from the end of the prefix array and produce a plausible but incorrect answer.

View full-size image ↗

The diagram labels boundaries separately from element positions. A prefix entry belongs before or after a span of values; confusing it with the value at the same numeric index is a common source of off-by-one errors.

Derive the formula from cancellation

By definition, prefix[right] contains every value before right. Those values split into the ones before left and the ones in [left, right). The first group totals prefix[left], so subtracting it leaves exactly the requested interval.

The argument works when left == right: both prefixes describe the same set of values and cancel to zero. It also works for a whole-array interval beginning at zero because the leading prefix is zero. No conditional branch is needed for either case.

Negative values do not invalidate the formula. They can make a later prefix smaller than an earlier one, as the total drops from four to three after reading minus one. The USACO Guide’s prefix-sum explanation develops the preprocessing and subtraction method for range queries.

Nondecreasing prefixes require nonnegative input values. If another algorithm uses binary search to find the first prefix above a threshold, it needs that extra assumption or another proof of monotonicity. Correct interval summation alone does not establish it.

Preprocessing pays off across many queries

Building the prefix array takes Θ(n) additions and Θ(n) storage. Each validated query then uses constant-time index access and one subtraction. For q queries on unchanged values, total work is Θ(n + q), compared with up to Θ(nq) work if every query scans its interval.

The bound assumes additions and subtractions have constant cost in the chosen number representation. Python can represent arbitrarily large integers, but arithmetic on them grows more expensive as their bit length grows. Fixed-width implementations need an accumulator wide enough for the largest possible total or an explicit overflow policy.

Floating-point values introduce another limitation. Prefix subtraction can lose precision when two large, nearly equal totals are subtracted to recover a small interval. If numeric error matters, choose an accumulation and storage strategy based on the value range and required accuracy. The algebraic identity remains correct over exact arithmetic; finite-precision calculations approximate it.

For only one short interval query, computing every prefix may do more work than scanning the requested slice. Prefix sums are a workload optimization, so count the expected query volume and interval lengths before adding another array.

Updates change a suffix of the prefix array

Changing the value at index i affects every prefix boundary after i. Updating a precomputed prefix array can therefore require Θ(n) writes. If values change frequently between queries, repeated rebuilding can erase the benefit of constant-time range lookup.

A Fenwick tree or segment tree trades a more involved representation for logarithmic updates and queries. The Fenwick-tree sum-query description explains how storing selected partial sums avoids touching the entire suffix after one change. The static prefix array is still simpler when the data is immutable or updates arrive in large batches between query phases.

The subtraction method also depends on the aggregate supporting cancellation. Prefix minima cannot answer an arbitrary range minimum by subtracting two values. For example, a small value before the requested interval can dominate both prefix minima while saying nothing about the minimum inside the interval. Associativity alone is not enough to justify a prefix-difference formula.

Test intervals as boundaries

For a small array, enumerate every pair 0 <= left <= right <= n and compare the prefix result with a direct sum of the slice. Include negative values, zeroes, an empty array, and intervals touching both ends. That test checks the boundary convention over all small ranges rather than selecting only a few convenient examples.

If an external API describes inclusive endpoints, convert [left, last] to [left, last + 1) at the boundary and check overflow or validity there. Keep the internal helper’s convention consistent. Mixing inclusive and exclusive endpoints inside the same formula is harder to review than one deliberate conversion at the caller.

Reproduce a small interval lost behind a large total

The floating-point limitation is visible without a large dataset. Put a value of 10**16 before two unit values. At that magnitude, a binary64 number cannot represent every integer, and adding one rounds back to the same stored total. Both additions can disappear during the prefix scan even though the requested interval contains two exact unit values.

import math

floating = [1e16, 1.0, 1.0]
floating_prefix = prefix_sums(floating)
assert floating_prefix == [0, 1e16, 1e16, 1e16]
assert range_sum(floating_prefix, 1, 3) == 0.0
assert math.fsum(floating[1:3]) == 2.0

exact = [10**16, 1, 1]
assert range_sum(prefix_sums(exact), 1, 3) == 2

careful_prefix = [math.fsum(floating[:end]) for end in range(4)]
assert careful_prefix[2] - careful_prefix[1] == 0.0

The array is finite and every value is nonnegative. Neither negative inputs nor a bad interval caused this failure. The exact cancellation proof assumes the stored prefixes equal their mathematical totals. Here the earlier rounding has already removed information before the subtraction takes place.

View full-size image ↗

Python’s math.fsum tracks multiple partial sums to reduce accumulated rounding error. It helps when summing the short interval directly, but using it independently for every prefix does not make every boundary exactly representable in one float. The mathematical total 10**16 + 1 still rounds when stored as binary64, so the final assertion cannot recover the single unit between boundaries one and two.

That careful_prefix construction is deliberately a tiny diagnostic, not the proposed preprocessing algorithm. It resums slices repeatedly and therefore performs quadratic total input work, plus slice allocation. Its purpose is to separate more careful accumulation from the precision of each stored result. Keeping a compensated accumulator during one pass has a different implementation and cost, but storing only one rounded number per boundary still needs an accuracy analysis.

Integer storage is suitable when the domain genuinely consists of discrete units such as event counts. Python’s arbitrary-size integers preserve the exact totals in this example, with the earlier bit-cost qualification. Multiplying an arbitrary float by a scale and converting it to an integer is not automatically exact: the application must define units and conversion rules before building the array. Decimal or rational arithmetic also has its own representation, precision and performance contract.

For a numerical exercise, move the large value to the end and compare the same small leading interval. Then vary its magnitude and record the first point where a unit increment is lost in the chosen floating representation. Compare results with an exact integer reference rather than a second implementation that repeats the same rounded arithmetic. This tests the numerical model separately from the boundary formula.

The helper accepts built-in integer endpoints and rejects booleans and fractional indices before indexing. It assumes the supplied prefix array was constructed under the intended arithmetic model; a bounds check cannot establish its contents or make stale prefixes consistent with changed source values. Keep construction, data version and query interpretation together when exposing this optimization through an application API.