Prefix sums

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.

Sources: Wikipedia: Prefix sum

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

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]
}

function buildPrefix(arr: number[]): number[] {
    const prefix: number[] = 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: number[], l: number, r: number): number {
    return prefix[r + 1] - prefix[l]; // sum of arr[l..r]
}

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]

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]
}

    public static int[] buildPrefix(int[] arr) {
        int[] prefix = new int[arr.length + 1];
        for (int i = 0; i < arr.length; i++) {
            prefix[i + 1] = prefix[i] + arr[i];
        }
        return prefix;
    }

    public static int rangeSum(int[] prefix, int l, int r) {
        return prefix[r + 1] - prefix[l]; // sum of arr[l..r]
    }

    public static int[] BuildPrefix(int[] arr) {
        var prefix = new int[arr.Length + 1];
        for (int i = 0; i < arr.Length; i++) {
            prefix[i + 1] = prefix[i] + arr[i];
        }
        return prefix;
    }

    public static int RangeSum(int[] prefix, int l, int r) {
        return prefix[r + 1] - prefix[l]; // sum of arr[l..r]
    }

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.

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;
}

When should you use Prefix sums?

Use Prefix sums when the problem statement says “many sum-over-a-range queries”, “answer several range-sum questions on the same array” or “sum from index l to r”. A solution built on it usually runs in O(n) build / O(1) query.

• •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

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is Prefix sums confused with?

Prefix sums is most often confused with Sliding window (fixed size), Difference array, Fenwick tree / segment tree and Hash set / map.

• 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.

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?

Interview problems solved with Prefix sums include Range sum query immutable, Subarray sum equals k, Find pivot index, Product of array except self, Continuous subarray sum, Maximum size subarray sum equals k and Range sum query 2D.

• 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.

What is the time and space complexity of Prefix sums?

The target complexity of Prefix sums is O(n) build / O(1) query.

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