Prefix Sums in Practice

Why prefix sums earn their place

Range queries are the most common shape of "give me a number that summarises a slice of the array." A naive answer recomputes the slice each time, for q queries on an array of n elements, that's O(q · n) operations, which becomes intolerable when q grows. Prefix sums collapse that to O(n + q): one linear scan to build the prefix table, then a single subtraction per query. The trick is small. Its reach is enormous.

The idea also surfaces a deeper habit: trade preprocessing for query speed. Whenever the same kind of question gets asked many times against an unchanging dataset, ask whether you can precompute something that makes each question cheap. Prefix sums are the simplest example; segment trees and sparse tables are the same idea taken further.

Construction with the off-by-one zero

The prefix table is one element longer than the input. P[0] = 0 represents "the sum of the empty prefix". P[i] for i > 0 represents the sum of the first i elements. With this convention, the sum of a[l..r), the half-open range from index l inclusive to r exclusive, is P[r] − P[l] for any 0 ≤ l ≤ r ≤ n, no special cases.

def build_prefix(a):
    P = [0] * (len(a) + 1)
    for i, x in enumerate(a):
        P[i + 1] = P[i] + x
    return P

def range_sum(P, l, r):       # sum of a[l..r), half-open
    return P[r] - P[l]

The sentinel zero is not decoration. Drop it and the formula breaks at l = 0. Half the bugs in homemade prefix code come from people writing P[i] = a[0] + ... + a[i] (closed prefix) and then trying to remember whether to subtract a[l] or not. The off-by-one zero pushes the messy decision into a one-time convention.

Problem 1. Range Sum Query Immutable

Given a fixed array, answer many queries of the form "sum from index l to r inclusive". The naive solution is O(n) per query; with prefix sums it's O(1) per query after O(n) construction.

class NumArray:
    def __init__(self, a):
        self.P = [0] * (len(a) + 1)
        for i, x in enumerate(a):
            self.P[i + 1] = self.P[i] + x

    def sumRange(self, l, r):  # inclusive on both ends
        return self.P[r + 1] - self.P[l]

The only subtlety is the inclusive convention the problem uses on the query, turn it into the half-open form by querying P[r + 1] - P[l]. This is a recurring nuisance: half the problems use closed ranges, half use half-open. Pick one form for your prefix table and translate at the boundary, never in the middle.

Problem 2. Subarray Sum Equals K

Now the question reverses. Instead of "what is the sum from l to r?" we ask "how many subarrays have sum exactly K?" Brute force iterates over all (l, r) pairs in O(n²). Prefix sums plus a hash map cuts it to O(n).

The key reframe: a subarray a[l..r) sums to K when P[r] − P[l] = K, i.e. P[l] = P[r] − K. Walking r forward, we ask "how many earlier indices had prefix sum equal to P[r] − K?", exactly the seen-so-far pattern from hash maps.

from collections import defaultdict

def subarray_sum(a, k):
    seen = defaultdict(int)
    seen[0] = 1                      # empty prefix counts
    running = count = 0
    for x in a:
        running += x
        count += seen[running - k]
        seen[running] += 1
    return count

The seed seen[0] = 1 is the empty prefix. It accounts for subarrays that start at index 0, without it, the algorithm silently undercounts in those cases. The total work is one pass through the array, with O(1) hash-map work per element: O(n) time, O(n) space.

Problem 3. Continuous Subarray Sum (modular)

Same shape, with modular arithmetic. "Does any subarray of length ≥ 2 sum to a multiple of K?" Two prefix sums with the same remainder modulo K differ by a multiple of K, so we look for two equal residues.

def check_subarray_sum(a, k):
    seen = {0: -1}                   # residue -> earliest index
    running = 0
    for i, x in enumerate(a):
        running = (running + x) % k
        if running in seen:
            if i - seen[running] >= 2:
                return True
        else:
            seen[running] = i
        # Note: we only insert the first occurrence; we want the longest
        # subarray and the earliest index gives that.
    return False

The "earliest index" rule is the wrinkle. We store residues in a hash map keyed by residue, mapping to the earliest index where that residue was seen. When the same residue reappears at index i, the subarray between them sums to a multiple of K and has length i − seen[residue]. The "≥ 2" constraint is the question's own; the prefix-sum machinery doesn't care about length.

Generalisations: XOR, counts, 2D

The technique is one identity, op(l..r) = op⁻¹(P[r], P[l]), applied wherever the operation has an inverse (or is its own inverse). XOR is its own inverse, so prefix XOR works the same way: xor(l..r) = P[r] XOR P[l]. Counts of "how many vowels in s[l..r]?" are sums over an indicator array.

In 2D, the same pattern lets you query the sum of any rectangle in O(1) after O(m·n) preprocessing. The inclusion-exclusion is one step longer: sum(r1..r2, c1..c2) = P[r2][c2] − P[r1][c2] − P[r2][c1] + P[r1][c1]. The corner-add at the end corrects for the rectangle counted twice during subtraction. Nothing about the idea is harder; only the bookkeeping is.

Where prefix sums break

The technique assumes the array is fixed. If updates can happen between queries, a naive prefix-sum rebuild costs O(n) per update, worse than the brute-force query. Mutable range sums need a different structure: a Fenwick tree (Binary Indexed Tree) for O(log n) point updates and range queries, or a segment tree for more complex operations.

The technique also assumes an invertible operation. Range minimum queries can't use prefix-min, there is no inverse for min. The right structure for range min is a sparse table (O(n log n) preprocess, O(1) query) or a segment tree.

Where beginners go wrong

• Closed-prefix convention. Storing P[i] = a[0] + ... + a[i] closed instead of half-open forces a special case at l = 0. The half-open P[0] = 0 form has zero special cases and is worth the one-line cost.
• Forgetting the empty-prefix seed. Subarray-sum-equals-K silently undercounts without seen[0] = 1. The empty prefix represents subarrays starting at index 0.
• Using prefix sums when the array is mutable. A single update invalidates the whole table. Reach for a Fenwick tree the moment updates appear.
• Writing 2D prefix without inclusion-exclusion. Subtracting just the two strips leaves the corner double-counted. The four-term formula is the correct one.

What to read next

The companion module (Arrays & Sequences) frames prefix sums as one of three transferable patterns. The Hash Maps & Sets module formalises the seen-so-far pattern that powers the subarray-sum-equals-K solution above. The Sliding Window in Depth deep-dive is the natural next step, it's a generalisation of the same pay-once-query-cheaply trade.