Prefix Sums in Python: Answering Range Queries in Constant Time

You have an array of a million daily sales figures and a dashboard that keeps asking "what did we take between day 12,000 and day 40,000?". Answering that by adding up 28,000 numbers is 28,000 additions per question. Ask forty different questions and you have done a million additions, most of them re-adding the same values you already added a moment ago.

Prefix sums remove that repetition with one move: compute every cumulative total once, up front, then answer any range sum with a single subtraction. Building the table costs O(n). Every query afterwards costs O(1) — two array reads and a minus sign — and that cost does not change whether the range covers 3 elements or 3 million.

The idea takes thirty seconds to write. The off-by-one takes most people an hour to stop getting wrong, so that is where this post spends its time first. After that, the same trick extends in three directions: rectangles in a 2D grid, range updates instead of range queries, and the hash-map version that counts subarrays summing to a target in linear time.

The idea

Take an array, and write down a second array that answers one question at every position: what is the total of everything before here?

That second array is the prefix sum array. For nums = [3, 1, 4, 1, 5, 9, 2, 6] it looks like this:

index      0    1    2    3    4    5    6    7    8
nums            3    1    4    1    5    9    2    6
prefix     0    3    4    8    9   14   23   25   31

Read it a column at a time. prefix[0] is 0, because the total of no numbers is zero. prefix[1] is 3, the total of the first one element. prefix[5] is 14, the total of the first five: 3 + 1 + 4 + 1 + 5. The rule that builds the whole thing is one line — prefix[i + 1] = prefix[i] + nums[i] — so each entry is its left neighbour plus one new value.

Two details look pedantic and are not.

The prefix array holds n + 1 entries, not n. Eight input numbers give nine cumulative totals. The extra one is the leading zero.

prefix[i] does not include nums[i]. It is the total of everything strictly to the left of index i. So a prefix entry describes the gap before an element rather than the element itself, which is exactly why the array needs one more slot than the input: there are nine gaps around eight numbers.

Now the payoff. The sum of nums[left..right], inclusive at both ends, is:

prefix[right + 1] - prefix[left]

prefix[right + 1] counts everything up to and including nums[right]; prefix[left] counts everything strictly before nums[left]. Both start from the front of the array, so subtracting cancels the shared front section and leaves exactly the elements from left to right.

Why the leading zero matters

Suppose you skip the sentinel and build a prefix array the same length as the input, where prefix[i] is the total of the first i + 1 elements. The query then reads prefix[right] - prefix[left - 1], and that expression is broken at left = 0.

In most languages prefix[-1] throws. In Python it does something worse: it returns the last element, which is the total of the entire array. The range sum comes back wrong, no exception is raised, and nothing points at the cause. You then patch it with if left == 0 and carry that special case everywhere.

The leading zero deletes the special case instead of handling it. prefix[0] is the sum of an empty range, which genuinely is zero, so left = 0 needs no different treatment from left = 5. That is the shape of a sentinel: one extra entry so the ordinary rule covers the boundary too.

Watching it work

Take the same array and ask for nums[2..5] — the values 4, 1, 5, 9, which add up to 19.

Look up two numbers:

• prefix[6] = 23. That is 3 + 1 + 4 + 1 + 5 + 9, the first six elements, which is everything up to and including nums[5].
• prefix[2] = 4. That is 3 + 1, everything strictly before nums[2].

Subtract: 23 − 4 = 19. The 3 + 1 at the front appears in both totals, so it cancels, and what is left is 4 + 1 + 5 + 9. One subtraction, no loop.

Now the awkward case, nums[0..3]: values 3, 1, 4, 1, total 9. The query is prefix[4] - prefix[0], which is 9 − 0 = 9. Nothing special happened. The zero at the front absorbed the boundary, exactly as designed.

One more, the single-element range nums[7..7]: prefix[8] - prefix[7] is 31 − 25 = 6, which is nums[7]. It works because adjacent prefix entries differ by exactly the element between them.

The code

The naive version first, so there is something to measure against.

def range_sum_naive(nums: list[int], left: int, right: int) -> int:
    """Add up nums[left..right] inclusive, one element at a time."""
    total = 0
    for index in range(left, right + 1):
        total += nums[index]
    return total


nums = [3, 1, 4, 1, 5, 9, 2, 6]
print(range_sum_naive(nums, 2, 5))
print(range_sum_naive(nums, 0, 3))

19
9

Correct, and the cost of every call is proportional to the width of the range. Here is the version that pays that cost once.

def build_prefix(nums: list[int]) -> list[int]:
    """Return prefix[i] = the sum of the first i values of nums.

    The result has len(nums) + 1 entries. prefix[0] is 0 — the sum of no
    values at all — and that sentinel is what makes every query a single
    subtraction with no special case for a range starting at index 0.
    """
    prefix = [0] * (len(nums) + 1)
    for index, value in enumerate(nums):
        prefix[index + 1] = prefix[index] + value
    return prefix


def range_sum(prefix: list[int], left: int, right: int) -> int:
    """Sum of nums[left..right] inclusive, from a prefix array."""
    return prefix[right + 1] - prefix[left]


prefix = build_prefix(nums)
print(prefix)
print(range_sum(prefix, 2, 5))
print(range_sum(prefix, 0, 3))
print(range_sum(prefix, 7, 7))
print(range_sum(prefix, 0, 7))

[0, 3, 4, 8, 9, 14, 23, 25, 31]
19
9
6
31

Those are the three cases from the walkthrough plus the whole array, and none needed a branch.

You rarely have to write build_prefix yourself. The standard library has had this since Python 3.2, and the initial argument that supplies the sentinel since 3.8:

from itertools import accumulate

print(list(accumulate(nums)))
print(list(accumulate(nums, initial=0)))
print(list(accumulate(nums, initial=0)) == build_prefix(nums))

[3, 4, 8, 9, 14, 23, 25, 31]
[0, 3, 4, 8, 9, 14, 23, 25, 31]
True

accumulate is a C-level loop, so it is faster than the Python for loop above and it is the version to reach for at work. Write build_prefix by hand only while you are learning it.

How the code maps to the idea

[0] * (len(nums) + 1) is the n + 1 rule made concrete. Allocating the exact size up front also means the loop only ever assigns to slots that already exist, so no append and no resizing.

prefix[index + 1] = prefix[index] + value is the one-line rule from the walkthrough. The + 1 on the left is what shifts the whole array right by one and leaves the sentinel untouched at index 0. Every entry is computed from the entry immediately before it, which is why one pass is enough — the work is never repeated.

prefix[right + 1] - prefix[left] is asymmetric on purpose, and that asymmetry is the whole off-by-one. The left end is exclusive in the prefix array and inclusive in the range, so it needs no adjustment; the right end is inclusive in the range, so it needs the + 1 to move past it. For half-open ranges — nums[left:right], matching Python slicing — the expression is the symmetric prefix[right] - prefix[left]. Pick one convention, put it in the docstring, and never mix the two.

Edge cases fall out of the arithmetic. An empty input gives [0], and there is no valid query to run against it. A range covering everything is prefix[n] - prefix[0], which the zero collapses to just prefix[n].

The values do not have to be positive. Nothing above assumes it — negative numbers and floats both work, though see the float warning further down.

Complexity

Build: O(n). The loop body runs exactly once per input element and does one addition and one store each time. Eight elements, eight additions. A million elements, a million additions. There is no nesting and no repeated work, so the count is exactly n.

Query: O(1). Two list index operations and one subtraction. Python lists are contiguous arrays of pointers, so indexing is a constant-time address calculation, not a walk. Three operations regardless of n and — the interesting part — regardless of how wide the range is. A range of 999,999 elements costs the same as a range of one.

Space: O(n). One extra list of n + 1 integers. That is a real cost, not a rounding error: for 10 million values you are holding a second 10-million-entry list.

There is no best or worst case to separate out here. The build loop runs exactly n iterations whatever the values are — no early exit, no branch that depends on the data — and a query does the same two lookups and one subtraction every time. Best, average and worst are the same bound, which is unusual and is exactly what makes the technique easy to reason about.

The trade only pays off when there are enough queries. Counting it exactly, for q queries whose ranges have total length L:

queries = [(0, 7), (2, 5), (1, 6), (3, 3), (0, 3)]

for left, right in queries:
    assert range_sum(prefix, left, right) == range_sum_naive(nums, left, right)

naive_additions = sum(right - left + 1 for left, right in queries)
print(f"naive:  {naive_additions} additions")
print(f"prefix: {len(nums)} additions to build + {len(queries)} subtractions "
      f"= {len(nums) + len(queries)}")

naive:  23 additions
prefix: 8 additions to build + 5 subtractions = 13

Eight elements and five queries is already a win, and the gap widens fast. With n = 1,000,000 and 100,000 queries averaging 30,000 elements each, the naive approach performs about 3 billion additions and the prefix approach performs 1.1 million operations — roughly 2,700 times fewer.

The other direction is worth stating too. For a single query over the whole array, the naive loop does n additions while the prefix version does n additions plus an allocation plus a subtraction — strictly worse. This is an amortisation: cheap queries bought with an upfront payment, and the break-even point is when L, the total length of all the queries, exceeds n + q.

Two dimensions: sums over a rectangle

The same idea works on a grid, and the payoff is bigger because a naive rectangle sum is quadratic in the rectangle's side length.

Take this 4 × 4 grid, and ask for the total of the rectangle from row 1 to row 2 and column 1 to column 3:

Build a table P where P[r][c] is the sum of every cell strictly above row r and strictly left of column c — the whole top-left block. Same convention as before: pad with a zero row and a zero column, so P is 5 × 5 for a 4 × 4 grid.

Each entry is built from three neighbours:

P[r+1][c+1] = grid[r][c] + P[r][c+1] + P[r+1][c] - P[r][c]

The block above and the block to the left both contain the block that is above and to the left, so that corner block gets counted twice and has to come off once. This is inclusion-exclusion, and it appears again in the query.

To read a rectangle from (top, left) to (bottom, right) inclusive, take the big block ending at its far corner, cut off the band above, cut off the band to the left, then add back the top-left block you have now removed twice:

P[bottom+1][right+1] - P[top][right+1] - P[bottom+1][left] + P[top][left]

def build_prefix_2d(grid: list[list[int]]) -> list[list[int]]:
    """Return prefix[r][c] = the sum of the block above and left of (r, c).

    Both dimensions get a leading zero row/column, so no query needs a
    boundary check.
    """
    rows, cols = len(grid), len(grid[0])
    prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
    for row in range(rows):
        for col in range(cols):
            # The block above and the block to the left overlap in the corner
            # block, so it is counted twice and has to come off once.
            prefix[row + 1][col + 1] = (
                grid[row][col]
                + prefix[row][col + 1]
                + prefix[row + 1][col]
                - prefix[row][col]
            )
    return prefix


def rectangle_sum(prefix: list[list[int]], top: int, left: int,
                  bottom: int, right: int) -> int:
    """Sum of the inclusive rectangle from (top, left) to (bottom, right)."""
    return (
        prefix[bottom + 1][right + 1]
        - prefix[top][right + 1]
        - prefix[bottom + 1][left]
        + prefix[top][left]
    )


grid = [
    [3, 0, 1, 4],
    [5, 6, 3, 2],
    [1, 2, 0, 1],
    [4, 1, 0, 1],
]
prefix_2d = build_prefix_2d(grid)
for row in prefix_2d:
    print(row)
print(rectangle_sum(prefix_2d, 1, 1, 2, 3))
print(rectangle_sum(prefix_2d, 0, 0, 3, 3))
print(rectangle_sum(prefix_2d, 2, 2, 2, 2))

[0, 0, 0, 0, 0]
[0, 3, 3, 4, 8]
[0, 8, 14, 18, 24]
[0, 9, 17, 21, 28]
[0, 13, 22, 26, 34]
14
34
0

Check the first answer by hand: the rectangle holds 6, 3, 2 on row 1 and 2, 0, 1 on row 2, which is 14. The formula gives 28 − 8 − 9 + 3 = 14. The second answer, 34, is the total of all sixteen cells; the third is the single cell at (2, 2), which is 0.

Cost. Building touches each of the rows × cols cells once and does three additions and subtractions per cell, so the build is O(rows × cols) — linear in the size of the grid, which is the least possible since every cell has to be read at least once. Each query is four lookups and three arithmetic operations: O(1), independent of the rectangle's area. Space is O(rows × cols) for the second table, and that is the real limit — a 10,000 × 10,000 grid needs a 100-million-entry prefix table.

The inverse problem: difference arrays

Prefix sums make many range reads cheap. Turn the problem around — many range writes, one read at the end — and the same relationship solves it backwards.

Say you have 8 slots, all starting at zero, and three updates: add 2 to indices 1 through 4, add 3 to indices 0 through 2, add 1 to indices 5 through 7. Done naively each update loops over its range, so k updates of average width w cost k × w writes.

Instead, record only the changes. Keep an array diff where diff[i] is how much the value jumps between index i - 1 and index i. Adding amount across [left, right] needs exactly two jumps: a step up at left, and a step back down just past right.

diff[left]      += amount     # from here on, everything is `amount` higher
diff[right + 1] -= amount     # past the right edge, take it back

Two writes per update, whatever the width. Then a single running sum over diff reconstructs the real values — and a running sum is a prefix sum, which is the whole point: the difference array is the inverse operation, so summing it undoes it.

Note that diff needs n + 1 slots again, this time for the opposite reason: an update whose right edge is the last index writes to diff[n], one past the end of the real data. That slot exists only to be ignored.

def build_difference(length: int, updates: list[tuple[int, int, int]]) -> list[int]:
    """Record each range update as two boundary changes, in O(1) per update."""
    diff = [0] * (length + 1)
    for left, right, amount in updates:
        diff[left] += amount        # from here on, every value is `amount` higher
        diff[right + 1] -= amount   # past the right edge, give it back
    return diff


def resolve(diff: list[int], length: int) -> list[int]:
    """Turn a difference array into the real values with one running sum."""
    return list(accumulate(diff[:length]))


def apply_updates_naive(length: int, updates: list[tuple[int, int, int]]) -> list[int]:
    """The obvious version: touch every index inside every range."""
    values = [0] * length
    for left, right, amount in updates:
        for index in range(left, right + 1):
            values[index] += amount
    return values


updates = [(1, 4, 2), (0, 2, 3), (5, 7, 1)]
diff = build_difference(8, updates)
print(diff)
print(resolve(diff, 8))
print(resolve(diff, 8) == apply_updates_naive(8, updates))

[3, 2, 0, -3, 0, -1, 0, 0, -1]
[3, 5, 5, 2, 2, 1, 1, 1]
True

Follow the running sum across [3, 2, 0, -3, 0, -1, 0, 0]: 3, 5, 5, 2, 2, 1, 1, 1. Adding the three updates by hand gives [3, 3, 3, 0, 0, 0, 0, 0] plus [0, 2, 2, 2, 2, 0, 0, 0] plus [0, 0, 0, 0, 0, 1, 1, 1], and those totals match — which is what the True on the last line asserts.

Cost. k updates at two writes each is O(k), then one pass to resolve is O(n): O(n + k) total, against O(n × k) in the worst case for the naive loop. The catch is that you cannot read a value until you have resolved, so this only works when every update arrives before any read. That restriction is exactly what makes it cheap.

The interview classic: subarray sum equals k

"How many contiguous subarrays add up to k?" is the problem that makes prefix sums click, because the naive answer is O(n²) and the fix is one hash map.

Every subarray nums[i..j] has sum prefix[j + 1] - prefix[i]. So asking for subarrays that sum to k is asking for pairs of prefix entries that differ by exactly k, with the earlier one first. Rewrite the condition:

prefix[j + 1] - prefix[i] = k, therefore prefix[i] = prefix[j + 1] - k

So walk the array once, keeping a running prefix sum. At each step, the number of subarrays ending here is the number of earlier prefix values equal to running - k. Keep a count of every prefix value seen so far in a dictionary, and that lookup is O(1) on average.

Try it on [3, 4, 7, 2, -3, 1, 4] with k = 7. The running prefix sums, sentinel included, are [0, 3, 7, 14, 16, 13, 14, 18], and exactly three ordered pairs differ by 7:

Those three pairs are the three subarrays: [3, 4], [7], and [7, 2, -3, 1].

from collections import defaultdict


def count_subarrays_with_sum(nums: list[int], target: int) -> int:
    """Count the contiguous subarrays of nums whose values add up to target."""
    counts: defaultdict[int, int] = defaultdict(int)
    counts[0] = 1        # the empty prefix, so a whole prefix can match on its own
    running = 0
    found = 0
    for value in nums:
        running += value
        # Every earlier prefix equal to running - target closes a subarray here.
        found += counts[running - target]
        counts[running] += 1
    return found


sample = [3, 4, 7, 2, -3, 1, 4]
print(count_subarrays_with_sum(sample, 7))
print(count_subarrays_with_sum([1, 1, 1], 2))
print(count_subarrays_with_sum([0, 0, 0], 0))

3
2
6

[1, 1, 1] with k = 2 has two answers, the first pair and the second. [0, 0, 0] with k = 0 has six, because all six subarrays sum to zero — three of length 1, two of length 2, one of length 3. That last case is what catches people who try to count with pointers instead.

Watch the counter run:

seen: defaultdict[int, int] = defaultdict(int)
seen[0] = 1
running = 0
for index, value in enumerate(sample):
    running += value
    print(f"i={index}  value={value:>3}  prefix={running:>3}  "
          f"want {running - 7:>3}  seen {seen[running - 7]} time(s)")
    seen[running] += 1

i=0  value=  3  prefix=  3  want  -4  seen 0 time(s)
i=1  value=  4  prefix=  7  want   0  seen 1 time(s)
i=2  value=  7  prefix= 14  want   7  seen 1 time(s)
i=3  value=  2  prefix= 16  want   9  seen 0 time(s)
i=4  value= -3  prefix= 13  want   6  seen 0 time(s)
i=5  value=  1  prefix= 14  want   7  seen 1 time(s)
i=6  value=  4  prefix= 18  want  11  seen 0 time(s)

The hit at i=1 is the one that needs counts[0] = 1. There, running is 7 and the algorithm looks for an earlier prefix of 0 — the sentinel, the empty prefix before the array starts. Without seeding the map you lose every subarray beginning at index 0, and the bug is invisible on test data whose answers all start later.

Cost. One pass, with one dictionary lookup and one dictionary write per element. Python dictionaries give O(1) average lookup, so the whole thing is O(n) average time and O(n) space. The map holds at most 2n + 1 entries: each step stores the prefix it just computed, and reading counts[running - target] on a defaultdict also inserts a zero for the value it failed to find.

Average is not a guarantee, and it is worth knowing why. In CPython a non-negative integer hashes to itself reduced modulo 2**61 - 1, and that is not randomised, so prefix sums chosen to share a hash really do drive each dictionary operation towards O(n) and the whole scan towards O(n²). Ordinary data never does that, but quote the O(n) as an average, not as a worst case.

This matters because the sliding window technique solves the same problem in O(1) space when every value is positive, since growing the window then always grows the sum. Add one negative number and that monotonicity is gone and the window breaks. Prefix sums plus a hash map do not care about signs at all.

When to use it, and when not to

Use prefix sums when the data is fixed and you will query it many times. Log analysis, dashboard ranges over historical data, sensor readings, precomputed lookup tables. The pattern to recognise: "given an array and q queries, each asking for a range".

Use a difference array when the updates all come before the reads — bulk range increments, interval booking counts, timeline aggregation.

Do not use it when the values change between queries. Updating nums[i] invalidates every prefix entry from i + 1 onwards, so a single element change costs O(n) to repair. If reads and writes interleave, reach for a Fenwick tree (binary indexed tree) or a segment tree: both give O(log n) point updates and O(log n) range sums. A prefix array is the degenerate case of those structures where you have decided updates never happen and bought O(1) queries with that promise.

Do not use it for a handful of queries. One or two range sums over a large array are cheaper computed directly than by building an n-entry table first.

Be careful with floats. Prefix sums of floating-point numbers accumulate rounding error along the whole array, and then the query subtracts two large, nearly equal totals — catastrophic cancellation, where the leading digits cancel and the error hiding beneath them becomes the answer's leading digits. For an accurate total of floats use math.fsum, which adds them exactly and rounds only once at the end. For range sums of floats, know that the error is proportional to the magnitude of the whole prefix, not just the range you asked about.

Integer overflow is not a Python problem — Python integers grow as needed — but it is the classic bug when you port this to C++, Java or Rust. A prefix sum over 100,000 values of up to a billion reaches 10^14, which overshoots the signed 32-bit maximum by a factor of about 46,000.

Where it shows up in the real world

Integral images in computer vision. A summed-area table is a 2D prefix sum, introduced by Frank Crow in 1984 for texture mapping and made famous by the Viola-Jones face detector in 2001. Every feature Viola-Jones scores is a difference of rectangle sums, and the integral image makes each of those rectangle sums four table lookups whatever the rectangle's size. Its detector holds a few thousand features arranged as a cascade of stages, and because most windows are rejected by the first stages only a handful of features are ever evaluated on a given window. A rectangle sum that costs the same at every scale is what made real-time face detection possible on 2001 hardware. OpenCV exposes it as cv2.integral to this day.

Running totals in databases and dataframes. SUM(amount) OVER (ORDER BY day ROWS UNBOUNDED PRECEDING) in PostgreSQL, SQL Server or BigQuery is a prefix sum computed by the engine in one pass. So are pandas.Series.cumsum and numpy.cumsum.

Weighted random choice in the Python standard library. random.choices(population, weights=...) calls itertools.accumulate on the weights to build a prefix array, then uses bisect to binary-search it for each pick. That is a prefix sum turning a weighted draw into a binary search over cumulative totals.

Parallel computing. Prefix sum is one of the fundamental parallel primitives, known there as scan. CUDA's Thrust library ships inclusive_scan and exclusive_scan, and they are the standard way to compute output offsets when many threads write variable-length results into one buffer: each thread's write position is the prefix sum of the sizes before it.

Common mistakes

Dropping the + 1 in the query. prefix[right] - prefix[left] gives you nums[left..right-1] — one element short at the right end. Fix: decide whether your range is inclusive or half-open, write it in the docstring, and test a single-element range, which fails loudly under both mistakes.

Building the prefix array without the sentinel. Then left = 0 needs prefix[-1], and in Python that silently reads the last element instead of raising. Always allocate n + 1 and start at zero.

Making the difference array length n. An update ending at the last index writes diff[n], so a length-n array raises IndexError on exactly the ranges that reach the end — often the last case anyone tests.

Forgetting the corner in 2D. Both the build step and the rectangle query need a corner term, and the signs are opposite: the build subtracts the block it counted twice, the query adds it back. Leave it out of the query and the answer is too small by the top-left block, which is correct-looking whenever top or left is 0 and wrong everywhere else. Test a rectangle that touches neither edge.

Missing counts[0] = 1 in the subarray counter. Every subarray that starts at index 0 is silently skipped. Test with [k] — a one-element array whose only element is the target, whose answer must be 1.

Mutating the input after building the prefix array. The prefix array is a snapshot. It goes stale the moment nums changes, and nothing warns you. If the data is mutable, either rebuild or use a Fenwick tree.

Practice

1. Given an array and a list of (left, right) queries, return the average of each range in O(1) per query.
2. Find an index where the sum of everything to its left equals the sum of everything to its right, in one pass over the array.
3. Given an array of only 0s and 1s, find the longest subarray with equal counts of each — map every 0 to −1 and look for two prefix sums that are equal.
4. Given a list of flight bookings, each (first_flight, last_flight, seats), return the total seats booked on every flight using a difference array.
5. Count the submatrices of a grid whose values sum to a target, by fixing a pair of rows and running the 1D subarray counter along the columns between them.

Summary

Prefix sums are the cheapest possible trade: one linear pass up front buys constant-time range sums forever after, as long as the data stops changing. Store n + 1 cumulative totals with a zero at the front, and every query is prefix[right + 1] - prefix[left] with no boundary cases to remember. The same relationship read backwards gives difference arrays, and the same relationship read as "pairs of prefix values k apart" gives the linear-time subarray counter.

Learn the n + 1 convention once and it will keep paying out, because the same off-by-one shows up in difference arrays, in 2D tables, and in every sliding-window variant that tracks a running total.

Keep reading

• The Sliding Window Technique — the other way to make subarray problems linear, and where it stops working.
• The Two Pointers Technique — the third member of this family of linear-scan tricks.
• Hash Tables in Python — why the dictionary lookup in the subarray counter is O(1), from the inside.
• Arrays and Dynamic Arrays — why indexing a Python list is constant time in the first place.
• Big O Notation — the counting arguments used above, done properly.