Lesson 5.1 · Prefix Sum

Running Totals and Range Sums

Build prefix[i] = sum of the first i elements; then the sum of a[l..r] is prefix[r + 1] − prefix[l].

12 min

Think of it like this

A car's odometer shows the total distance since it was built. To know how far you drove between Guwahati and Shillong, you don't re-measure the road: you subtract the reading at Guwahati from the reading at Shillong. A prefix sum array is an odometer for an array.

1.Building the prefix array

Use an array one longer than the input: prefix[0] = 0 and prefix[i + 1] = prefix[i] + a[i]. So prefix[i] is the sum of the first i elements (indexes 0..i−1).

The extra leading 0 removes special cases: the range starting at index 0 needs no if.

▶ Dry run: Building prefix sumsa = [3, 1, 4, 1, 5]

Step 1/5prefix[0] = 0: the sum of no elements.

2.Why it's worth it

Building costs O(n) once. Each query then costs O(1). With q queries, that's O(n + q) instead of O(n · q) for summing each range in a loop.

Prefix.java

public class Main {
    public static void main(String[] args) {
        int[] a = {3, 1, 4, 1, 5};
        int[] prefix = new int[a.length + 1];
        for (int i = 0; i < a.length; i++) prefix[i + 1] = prefix[i] + a[i];

        int l = 1, r = 3;
        System.out.println("sum of a[1..3] = " + (prefix[r + 1] - prefix[l]));
        System.out.println("sum of all = " + prefix[a.length]);
    }
}

Output

sum of a[1..3] = 6
sum of all = 14

Quick check

Using the prefix array p = [0, 3, 4, 8, 9, 14], what is the sum of a[2..4]?

Remember

prefix has length n + 1 with prefix[0] = 0.
sum(l..r) = prefix[r + 1] − prefix[l].
O(n) build, O(1) per query.

Common mistakes

Off-by-one between prefix[r] and prefix[r + 1].
Using int when sums can exceed about 2 × 10⁹.

Command Palette

Running Totals and Range Sums

1.Building the prefix array

2.Why it's worth it