---
title: "Prefix Sums"
description: "Build running totals once, then answer any range sum with one subtraction."
source: https://vizlearn.app/algorithms/search/prefix-sums
---

# Prefix Sums

Prefix sums turn repeated range-sum queries into constant-time work. One pass over the array writes a running total, `prefix[k] = nums[0] + … + nums[k − 1]`; after that, the sum of any contiguous range `nums[l..r]` is `prefix[r + 1] − prefix[l]`. That is two reads and one subtraction, whether the range covers one cell or the whole array.

Think of the odometer on a road trip. Write down the reading at every town, and you never re-drive a stretch to learn how long it is: the distance from town 2 to town 6 is one reading minus another. Prefix sums do the same for an array. The work moves out of the question and into one bookkeeping pass done up front.

## How Prefix Sums Work

Picture a fence between every pair of neighbouring cells, plus one before the first cell and one after the last. An array of `n` values has `n + 1` fences, numbered 0 to `n`. Then `prefix[k]` is the total of everything left of fence `k`. Fence 0 has nothing to its left, so `prefix[0] = 0`, and `prefix[n]` is the sum of the whole array.

Building the array is one loop. Each entry is the previous entry plus the cell that just passed: `prefix[k] = prefix[k − 1] + nums[k − 1]`. That is `n` additions, done once.

A query for `nums[l..r]`, inclusive on both ends, needs the two fences that bracket the range: fence `l` sits just before `nums[l]`, and fence `r + 1` sits just after `nums[r]`. Everything left of fence `r + 1`, minus everything left of fence `l`, leaves exactly the range. The shared part `nums[0..l − 1]` cancels. The query is one line with no loop, and its cost does not depend on `r − l`.

The leading zero earns its slot. Without `prefix[0] = 0`, a query that starts at `l = 0` would have nothing to subtract and would need its own branch. With it, `sum(0..r) = prefix[r + 1] − prefix[0]` falls out of the same formula.

The trick does not care about signs. Negative values just make the running total dip; the
subtraction still cancels the shared part exactly. The greedy shrink in the minimum-length
Sliding Window lesson relies on non-negative values.
Fixed-length sliding windows do not have that restriction; prefix sums also work with signed
values.

The price shows up when the array changes. Every `prefix[k]` with `k > i` includes `nums[i]`, so changing one value makes all `n − i` later entries stale. Each must be shifted by the same `delta = new − old` before the next query can trust the row.

## Prefix Sums Step by Step

The default input is `nums = [3, 1, 4, -2, 5, 9, 2, 6]` with four queries: `sum(2..5)`, `sum(0..7)`, `sum(4..4)` and `sum(1..6)`.

**Start with the question.** What is `sum(2..5)`? Reading `4`, `−2`, `5` and `9`
one by one gives running totals `4 → 2 → 7 → 16`: four reads. Now ask for `sum(0..7)`.
A direct sum starts another scan. The prefix table stores work you can reuse between queries.
The opening scan demonstrates the direct method; the comparison below uses the four queries
on the same array.

**Build.** Start with `prefix[0] = 0`, then add one cell per step:

1. `prefix[1] = 0 + 3 = 3`
2. `prefix[2] = 3 + 1 = 4`
3. `prefix[3] = 4 + 4 = 8`
4. `prefix[4] = 8 + (−2) = 6`. The total dips; nothing breaks.
5. `prefix[5] = 6 + 5 = 11`
6. Steps 6–8 continue the same way: `20`, `22`, `28`.

The finished row is `prefix = [0, 3, 4, 8, 6, 11, 20, 22, 28]`, built with 8 additions.

**Query.** Each query reads two entries:

1. `sum(2..5) = prefix[6] − prefix[2] = 20 − 4 = 16`. Summing directly would read 4 cells.
2. `sum(0..7) = prefix[8] − prefix[0] = 28 − 0 = 28`. The whole array, still 2 reads; this is where the leading zero pays off.
3. `sum(4..4) = prefix[5] − prefix[4] = 11 − 6 = 5`. A single cell, still 2 reads.
4. `sum(1..6) = prefix[7] − prefix[1] = 22 − 3 = 19`. Six cells, 2 reads.

Summing each range directly would read `4 + 8 + 1 + 6 = 19` cells. The prefix version reads 8 entries for the queries, plus the 8 additions it spent once on the build.

On the canvas, `prefix[k]` sits below fence `k`. The first two additions keep the old total
and the incoming value in focus together. The first query then reads the right total, reads
the left total, and cancels the cells they share before holding the answer. The bars mark
covered positions, not numerical magnitude: a long span can still sum to 0. Later queries
repeat the same rule more quickly. At the bottom, `prefix reads` stays at 2 while
`direct reads` changes from 4 to 8 to 1 to 6.

Load the **Point update** scenario to see the other side. After `sum(0..5) = 20`, `nums[1]` changes from 1 to 7 (`Δ = +6`). The entries `prefix[2..8]` turn stale, and the repair loop rewrites all seven of them before the same query, asked again, returns 26.

## Time and Space Complexity

| Operation | Time |
|---|---|
| Build | O(n) |
| Range-sum query | O(1) |
| Point update (as animated) | O(n − i), O(n) worst case |
| Direct range sum, for comparison | O(r − l + 1) |

Space is O(n) for the `n + 1` prefix entries. Repeated long-range queries on a mostly unchanged
array can repay the initial build. A single-cell query already needs only one direct read,
so two prefix reads are not automatically cheaper. With `q` queries on a fixed array, the
total time complexity is O(n + q) instead of O(n · q) in the worst case.

When updates are frequent, a plain prefix array is the wrong tool. A Fenwick tree (binary indexed tree) or a segment tree answers range sums and point updates in O(log n) each. The lesson animates the plain array so the update cost is visible rather than hidden.

## Edge Cases

- **Range starting at index 0.** `sum(0..r) = prefix[r + 1] − prefix[0]`, and `prefix[0] = 0`. No special branch.
- **Single-cell range.** `sum(i..i) = prefix[i + 1] − prefix[i] = nums[i]`. Still two reads.
- **The whole array.** `sum(0..n − 1) = prefix[n]`. The last entry holds the grand total.
- **Negative values.** Totals can fall as well as rise; answers stay exact. The default run dips from 8 to 6.
- **Equal prefix values.** If `prefix[a] = prefix[b]`, the range `nums[a..b − 1]` sums to 0. The **Equal totals** scenario shows three such ranges in one array, which is the starting point for "count subarrays that sum to k".
- **Update at the first or last index.** Changing `nums[0]` rewrites all `n` later entries; changing `nums[n − 1]` rewrites only `prefix[n]`.

## Common Mistakes

- **Using `prefix[r] − prefix[l]` for an inclusive range.** That drops `nums[r]`. The right fence of `nums[l..r]` is `r + 1`, which is why the prefix array has `n + 1` entries.
- **Storing the sum through `nums[k]` with no leading zero.** The array is one entry shorter and every `l = 0` query needs an `if`. Off-by-one bugs tend to collect around that branch.
- **Rebuilding inside the query.** Calling `build(nums)` once per query, or summing `nums[l:r + 1]` in the loop, brings back O(n) per query. Build once, reuse the array.
- **Forgetting the array is a snapshot.** After `nums[i]` changes, every `prefix[k]` with `k > i` is stale. Either repair them all with `prefix[k] += delta` or switch to a Fenwick tree.
- **Ignoring overflow on long inputs.** In languages with fixed-width integers, the running total can exceed the type even when every single value fits. Use a wider type for the prefix array.