Prefix Sum

You already use this pattern every time you read a bank statement. The statement does not store the total spent between the 8th and the 19th; it stores a running balance, and if you want the sum over that stretch you subtract the balance on the 8th from the balance on the 19th. That is the entire idea. Precompute a running total once, and any range sum becomes a single subtraction instead of a fresh loop.

The reason it matters is repeated queries. Summing a range naively is fine once. Do it for thousands of ranges over the same array and you are re-walking the same elements again and again, when one preprocessing pass could have made every query constant time.

Turning range sums into subtractions

Build an array where prefix[i] holds the sum of everything up to index i. Then the sum from start to end is prefix[end] - prefix[start - 1], because the second term cancels exactly the part you did not want.

def build_prefix(arr):
    prefix = [0] * len(arr)
    prefix[0] = arr[0]
    for i in range(1, len(arr)):
        prefix[i] = prefix[i - 1] + arr[i]
    return prefix

def range_sum(prefix, start, end):
    if start == 0:
        return prefix[end]
    return prefix[end] - prefix[start - 1]

On the toy input sales = [100, 200, 150, 300, 250], the prefix array is [100, 300, 450, 750, 1000], and the sum of days 1 through 3 is prefix[3] - prefix[0] = 750 - 100 = 650. One subtraction, no matter how wide the range. Building the prefix is O(n) once; every query after that is O(1).

The sales array 100 200 150 300 250 drawn above its running totals 100 300 450 750 1000; the sum of days one through three, which is 200 plus 150 plus 300 equals 650, is computed as prefix at index three minus prefix at index zero, that is 750 minus 100, cancelling the days before the range and leaving exactly its total.

In the wild: finding a stretch that nets to zero

The subtraction view unlocks something less obvious. Suppose you have a ledger of daily net changes, deposits positive and withdrawals negative, and you want to know whether some contiguous run of days cancels out exactly, leaving the balance where it started. Two days bound a zero-sum stretch precisely when their running totals are equal, because the sum between them is the difference of those two totals. So sweep once, remember every running total you have seen, and the first repeat is your answer:

def has_zero_sum_stretch(changes):
    seen = {0}          # a running total of 0 exists before any day
    running = 0
    for x in changes:
        running += x
        if running in seen:
            return True         # this total occurred before, the gap between sums to zero
        seen.add(running)
    return False

This is still prefix sums, read from the other side. Instead of subtracting two prefixes to measure a range, you hunt for two prefixes that are already equal, because equal running totals are the definition of a zero-sum range. It is the same class of problem as the bank-statement query, just asked in reverse. Swap the target from zero to any k, store the totals in a dictionary and look for running - k, and the same one pass finds a contiguous stretch summing to k. That single trick is the backbone of a whole family of subarray problems, and it is why prefix sums plus a hashmap show up constantly in real analytics and reconciliation code.

The trigger

Repeated range queries over data that does not change, or a question about a contiguous stretch summing to a target. If you catch yourself about to write a loop that re-sums overlapping ranges, that is the tell. Precompute once, subtract forever.

Where it shows up

  • Range sum, average, or count queries answered in constant time after one pass.
  • Subarray sums: does a contiguous run sum to k, how many do, what is the longest that sums to zero. Prefix sums plus a hashmap own this territory.
  • 2D prefix sums for sums over rectangular regions of a grid, the workhorse behind fast box blurs and integral images in graphics.

Where it bites

The off-by-one on prefix[start - 1] is the classic wound: when start is zero there is no prefix[-1] you want (Python will happily hand you the last element instead), so guard that boundary explicitly. And prefix sums assume the data is static. If values are updated between queries, a plain prefix array forces a full rebuild, and you should reach for a Fenwick or segment tree instead.

When to skip the precompute

A prefix sum is an investment: O(n) time and O(n) memory up front, repaid only if you ask enough range questions to earn it back. For a single query, the plain loop is simpler and wins outright. It also assumes the data holds still; if values change between queries, every edit invalidates the array, and a Fenwick or segment tree is the honest choice instead. And it answers totals, not extrema: a prefix array cannot hand you the minimum of a range, so do not reach for it when the question is about max or min rather than sum.

Where it connects

Prefix sums make Sliding Window even cheaper when the window's quantity is a plain sum, and they pair with Hashmaps and Frequency Counting for the subarray-sum family above. They also sit underneath a lot of range-based Dynamic Programming, where the running total you precompute is the first layer the recurrence builds on.

References