Prefix sums in Python: pay once, answer static range totals quickly

Problem. A program that repeatedly totals slices of one unchanged list repeats nearly the same additions. Baseline complexity. For query width w, sum(values[left:right]) visits w values, so many queries cost the sum of their widths and also create temporary slices. Solution. Store an exclusive prefix total once, then subtract two totals for each half-open interval. Measured result. On this Raspberry Pi run, 8,000 queries over 200,000 values took 3.976 seconds with repeated slices and 0.00635 seconds with prefix lookups, a 626.48× best-sample ratio after a 0.0331-second build.

Reproduce the result

Complete code

from __future__ import annotations
import gc
import json
import platform
import random
import sys
import timeit
import tracemalloc
SEED = 20260831
VALUE_COUNT = 200_000
QUERY_COUNT = 8_000
REPEATS = 5
def make_data() -> tuple[list[int], list[tuple[int, int]]]:
    rng = random.Random(SEED)
    values = [rng.randrange(-50, 51) for _ in range(VALUE_COUNT)]
    queries = []
    for _ in range(QUERY_COUNT):
        left = rng.randrange(0, VALUE_COUNT - 20_000)
        width = rng.randrange(2_000, 20_001)
        queries.append((left, left + width))
    return values, queries
def sum_each_range(values: list[int], queries: list[tuple[int, int]]) -> int:
    total = 0
    for left, right in queries:
        total += sum(values[left:right])
    return total
def build_prefix_sums(values: list[int]) -> list[int]:
    prefix = [0]
    running_total = 0
    for value in values:
        running_total += value
        prefix.append(running_total)
    return prefix
def sum_with_prefix(prefix: list[int], queries: list[tuple[int, int]]) -> int:
    total = 0
    for left, right in queries:
        total += prefix[right] - prefix[left]
    return total
def time_samples(callable_) -> list[float]:
    timer = timeit.Timer(callable_)
    return timer.repeat(repeat=REPEATS, number=1)
def traced_prefix_build(values: list[int]) -> tuple[list[int], int]:
    tracemalloc.start()
    prefix = build_prefix_sums(values)
    _, peak = tracemalloc.get_traced_memory()
    tracemalloc.stop()
    return prefix, peak
def main() -> None:
    values, queries = make_data()
    prefix, prefix_peak_bytes = traced_prefix_build(values)
    baseline_result = sum_each_range(values, queries)
    prefix_result = sum_with_prefix(prefix, queries)
    assert baseline_result == prefix_result
    assert len(prefix) == len(values) + 1
    assert sum_with_prefix(prefix, [(0, 0), (0, len(values))]) == sum(values)
    gc.collect()
    prefix_build_samples = time_samples(lambda: build_prefix_sums(values))
    gc.collect()
    baseline_samples = time_samples(lambda: sum_each_range(values, queries))
    gc.collect()
    prefix_samples = time_samples(lambda: sum_with_prefix(prefix, queries))
    items_summed = sum(right - left for left, right in queries)
    baseline_best = min(baseline_samples)
    prefix_best = min(prefix_samples)
    result = {
        "correctness": {
            "all_query_totals_equal": True,
            "empty_and_full_range_checked": True,
            "combined_total": baseline_result,
        },
        "input": {
            "seed": SEED,
            "values": VALUE_COUNT,
            "queries": QUERY_COUNT,
            "query_width_range": [2_000, 20_000],
            "items_summed_by_baseline": items_summed,
            "prefix_reads_by_optimised_queries": QUERY_COUNT * 2,
        },
        "timing_seconds": {
            "repeats": REPEATS,
            "prefix_build": prefix_build_samples,
            "baseline_range_sum": baseline_samples,
            "prefix_range_sum": prefix_samples,
            "best_baseline_to_prefix_ratio": baseline_best / prefix_best,
        },
        "memory": {
            "prefix_build_peak_traced_bytes": prefix_peak_bytes,
            "tracing_scope": "prefix list construction only; input values, queries, imports, native allocations and RSS excluded",
        },
        "environment": {
            "python": sys.version.split()[0],
            "implementation": platform.python_implementation(),
            "platform": platform.platform(),
        },
    }
    print(json.dumps(result, indent=2, sort_keys=True))
if __name__ == "__main__":
    main()

Output

{
  "correctness": {
    "all_query_totals_equal": true,
    "combined_total": 4591094,
    "empty_and_full_range_checked": true
  },
  "environment": {
    "implementation": "CPython",
    "platform": "Linux-6.12.47+rpt-rpi-v8-aarch64-with-glibc2.41",
    "python": "3.13.5"
  },
  "input": {
    "items_summed_by_baseline": 87940437,
    "prefix_reads_by_optimised_queries": 16000,
    "queries": 8000,
    "query_width_range": [
      2000,
      20000
    ],
    "seed": 20260831,
    "values": 200000
  },
  "memory": {
    "prefix_build_peak_traced_bytes": 7905360,
    "tracing_scope": "prefix list construction only; input values, queries, imports, native allocations and RSS excluded"
  },
  "timing_seconds": {
    "baseline_range_sum": [
      4.075982055976056,
      3.9758412720402703,
      4.05186126800254,
      4.018912757979706,
      4.022087166085839
    ],
    "best_baseline_to_prefix_ratio": 626.478806304224,
    "prefix_build": [
      0.0350092020817101,
      0.0330993999959901,
      0.03330850903876126,
      0.033080954919569194,
      0.033270825049839914
    ],
    "prefix_range_sum": [
      0.006562477094121277,
      0.0063463300466537476,
      0.006609715986996889,
      0.007477618055418134,
      0.006601419998332858
    ],
    "repeats": 5
  }
}

Environment

The program ran with CPython 3.13.5 on Linux 6.12.47+rpt-rpi-v8-aarch64-with-glibc2.41. It uses only the standard library. Run it with python3 prefix_sum_benchmark.py from its directory.

Methodology

A seeded generator made 200,000 integers and 8,000 half-open queries, each 2,000 to 20,000 items wide. Both functions had to return the same combined total, and empty and full ranges were checked before timing. timeit.Timer.repeat ran each callable once in five repeats; the article reports the fastest repeat and preserves every sample in the captured output. Python’s timeit is intended for small code timings and disables garbage collection by default, which improves comparability but means these measurements are not a model of a busy application.^[2] The prefix allocation probe starts tracing immediately before construction, so it excludes the inputs, imports, native allocations and process resident memory.^[3]

The problem is repeated range work

A dashboard, an accounting export or a batch validator may ask for many totals from one list that does not change during the batch. The direct expression is wonderfully readable:

sum(values[left:right])

It is also honest about its cost. A range of 12,000 items needs 12,000 additions. Asking again for an overlapping range starts over, even though most of the earlier work is sitting there, looking slightly smug.

A prefix sum records the cumulative total before each position. With an initial zero, prefix[i] is the sum of values[0:i]. The total of values[left:right] is therefore prefix[right] - prefix[left]. This is the standard static-range-sum construction: one linear preprocessing pass followed by constant-time queries.^[1]

What the complexity claim does, and does not, say

For n values and q queries, the direct implementation takes O(sum of query widths) time. Its worst case is O(nq). The prefix version takes O(n) to build and O(q) to answer the queries, with O(n) extra stored totals.^[1]

That is theoretical work. The Python code has its own costs. values[left:right] creates a list slice before sum consumes it, while the prefix list stores one extra integer reference per input position and may create new integer objects as cumulative totals grow. In this run, building that list reached 7,905,360 traced bytes. That is a Python-allocation peak within the chosen tracing window, not an RSS measurement and not a promise about another interpreter.^[3]

The operation count explains the direction of the result without pretending to explain every microsecond. The baseline summed 87,940,437 items across the generated queries. The prefix query loop read two stored totals per query, 16,000 reads in total. The measured gap is specific to long, repeated ranges on this machine; a workload dominated by one short query has little opportunity to repay the setup.

The identity behind the lookup

The extra leading zero keeps Python’s half-open indexing pleasant. For left = 0, the expression becomes prefix[right] - prefix[0], and prefix[0] is zero. There is no special first-range branch waiting behind a curtain.

For a fixed list, the identity is exact for integers:

sum(values[left:right]) == prefix[right] - prefix[left]

The example deliberately uses integer values. Floating-point addition changes rounding when terms are grouped differently, so an equivalent prefix technique may produce a slightly different last bit from repeated summation. That is a correctness question, not a performance footnote.

When not to use it

Prefix sums suit static data and an operation with a usable inverse. Addition works because a range total can be recovered by subtraction. A plain prefix maximum cannot remove the effect of an old maximum, so the same subtraction trick does not answer arbitrary maximum queries.

Updates are the other limit. Changing values[k] invalidates every later prefix total. A workload with frequent updates needs a data structure designed to update partial totals, and that brings more implementation work than one plain list. For a single total, a short list, or data that changes before every query, the direct sum is usually the clearer choice.

The useful decision rule is modest: build prefix sums when the values remain fixed for a batch and the batch has enough range queries to repay one pass and one additional list. The benchmark shows what that looked like for deliberately wide ranges, not an all-purpose speed badge.

Sources

[1] USACO Guide: Introduction to Prefix Sums

[2] Python documentation: timeit

[3] Python documentation: tracemalloc