---
title: "Prefix sums"
url: https://algopath.pro/patterns/prefix-sums
language: en
summary: "Store a running total of everything that comes before each index. A range sum then costs one subtraction instead of a loop."
updated: 2026-08-24
---

# Prefix sums

Store a running total of everything that comes before each index. A range sum then costs one subtraction instead of a loop.

## How does Prefix sums work?

Make an array one slot longer than the input. Slot zero is the sum of nothing, so it is zero.

Walk the input from left to right. Each slot holds the previous total plus the current value.

Now prefix[i] means the sum of the first i values. Nothing from index i onward is included.

A range from l to r is the whole prefix up to r. Subtract the part that sits before l.

So the answer is prefix[r + 1] minus prefix[l]. That is one subtraction, whatever the width.

The array is built once and read many times. It stops being valid if a value changes.

- `prefix = [0]` The input is [3, 1, 4, 1]. Slot zero is the sum of nothing.
- `prefix = [0, 3]` Add the first value. One element sums to 3.
- `prefix = [0, 3, 4]` Add 1 to the running total. Two elements sum to 4.
- `prefix = [0, 3, 4, 8, 9]` The rest finishes the array. Building it took one pass.
- `sum(1..2) = 8 - 3 = 5` That range holds 1 and 4. One subtraction, no loop.

## When should you use Prefix sums?

- many sum-over-a-range queries
- answer several range-sum questions on the same array
- sum from index l to r
- running total or cumulative sum

## What is Prefix sums confused with?

- **Sliding window (fixed size)** - A window answers about one span that keeps moving. Prefix sums answer about any span you name.
- **Difference array** - That is the mirror image: many range writes, one read at the end. Here it is many reads.
- **Fenwick tree / segment tree** - A prefix array breaks the moment a value changes. A Fenwick tree pays log n to allow updates.
- **Hash set / map** - A map has no notion of a range at all. Counting subarrays needs the running total beside it.

## What is the time and space complexity of Prefix sums?

n up to 1e6 with many range queries gives O(n) setup. Each query then costs O(1), plus O(n) memory.

## A worked example of Prefix sums

### Count the subarrays that sum to k

You get an array of integers and a number k. Count the contiguous stretches that sum to exactly k.

Values can be negative, so a sliding window cannot shrink safely.

Walk the array and keep a running total.

A stretch ending here sums to k when some earlier prefix equals total minus k. A map of seen prefixes counts them.

```javascript
function subarraySum(nums, k) {
    const seen = new Map([[0, 1]]); // one empty prefix, total zero
    let total = 0;
    let count = 0;

    for (const x of nums) {
        total += x;

        // an earlier prefix of total - k closes a stretch that sums to k
        count += seen.get(total - k) ?? 0;
        seen.set(total, (seen.get(total) ?? 0) + 1);
    }

    return count;
}
```

## Common mistakes with Prefix sums

- **Skipping the leading zero** A range starting at index zero then has nothing to subtract. The array needs n plus one slots.
- **Off by one at the right edge** The sum from l to r reads prefix[r + 1]. Reading prefix[r] drops the last value.
- **Changing a value afterwards** One edit invalidates every slot after it. Use a Fenwick tree when updates are mixed in.
- **Letting the total overflow** A million values near 1e9 pass the safe integer range. Switch to BigInt or a wider type.

## Which interview problems use Prefix sums?

- **Range sum query immutable** Build once, then answer each query with one subtraction.
- **Subarray sum equals k** Pair the running total with a map of earlier prefixes.
- **Find pivot index** The left sum must equal the total minus the left sum minus the value.
- **Product of array except self** The same idea with prefix and suffix products.
- **Continuous subarray sum** Store the prefix totals modulo k instead of the raw totals.
- **Maximum size subarray sum equals k** Keep the first index where each prefix appeared.
- **Range sum query 2D** Two dimensions, four lookups per query.

## JavaScript

```javascript
function buildPrefix(arr) {
    const prefix = new Array(arr.length + 1).fill(0);
    for (let i = 0; i < arr.length; i++) {
        prefix[i + 1] = prefix[i] + arr[i];
    }
    return prefix;
}
function rangeSum(prefix, l, r) {
    return prefix[r + 1] - prefix[l]; // sum of arr[l..r]
}
```

## Python

```python
def build_prefix(arr):
    prefix = [0] * (len(arr) + 1)
    for i, val in enumerate(arr):
        prefix[i + 1] = prefix[i] + val
    return prefix

def range_sum(prefix, l, r):
    return prefix[r + 1] - prefix[l]  # sum of arr[l..r]
```

## PHP

```php
function buildPrefix(array $arr): array {
    $prefix = array_fill(0, count($arr) + 1, 0);
    foreach ($arr as $i => $val) {
        $prefix[$i + 1] = $prefix[$i] + $val;
    }
    return $prefix;
}
function rangeSum(array $prefix, int $l, int $r): int {
    return $prefix[$r + 1] - $prefix[$l]; // sum of arr[l..r]
}
```