Lesson 7 · Linear structures

Prefix Sums

A prefix sum array stores the cumulative sum of elements from the beginning of an array up to every index. It allows you to answer multiple range sum queries in O(1) time after a single O(N) preprocessing step.

The Naive Approach vs Prefix Sum

If you are asked to find the sum of elements between index L and index R multiple times, a naive approach loops from L to R for every query, taking O(N) time per query.

By taking O(N) time upfront to build a prefix sum array, you can answer an unlimited number of subsequent queries in just O(1) time each.

Naive queries are too slow for many lookups
Prefix sums trade space for extreme speed
Classic example of preprocessing

Building the Array

To build a prefix sum array P for an input array A, we define P[i] as the sum of all elements from A[0] to A[i].

This can be computed iteratively: P[0] = A[0], and for i > 0, P[i] = P[i-1] + A[i]. Often, P is made 1 element larger than A (with P[0] = 0) to handle edge cases cleanly.

Requires an extra array of size N or N+1
Built in a single linear pass
Can be done in-place to save memory

Key reference

Terms, operations, and practical uses

Core mechanics

Cumulative SumThe running total of a sequence. The prefix sum at index i is the sum of all elements from index 0 to i.
Range QueryAsking for the sum of elements between two specific indices, L and R.
PreprocessingTaking O(N) time upfront to build a data structure so that future queries are extremely fast.

Implementation details

1-Based IndexingPadding the prefix sum array with a 0 at the start to avoid out-of-bounds errors when querying from the very beginning of the array.
In-Place ModificationOverwriting the original input array with prefix sums to save O(N) auxiliary space, acceptable if original data isn't needed.
Invertible OperationAn operation that can be 'undone'. Prefix sums require subtraction; prefix XORs require XOR. Min/Max are not invertible.

Advanced variations

2D Prefix SumExtending the concept to a grid. The prefix sum at (r, c) contains the sum of the rectangle from (0,0) to (r,c).
Prefix ProductsMultiplying elements instead of adding. Requires division to answer queries, and special handling if zeroes are present.
Suffix SumsThe reverse of a prefix sum. The sum of all elements from the current index to the end of the array.

Code example

Building a Prefix Sum Array

A = [3, 1, 4, 1, 5, 9]
P = [0] * len(A)
P[0] = A[0]

for i in range(1, len(A)):
    P[i] = P[i-1] + A[i]

print('Prefix sum array:', P)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> A = {3, 1, 4, 1, 5, 9};
    vector<int> P(A.size());
    P[0] = A[0];

    for (int i = 1; i < A.size(); i++) {
        P[i] = P[i-1] + A[i];
    }
    return 0;
}

class Main {
    public static void main(String[] args) {
        int[] A = {3, 1, 4, 1, 5, 9};
        int[] P = new int[A.length];
        P[0] = A[0];

        for (int i = 1; i < A.length; i++) {
            P[i] = P[i-1] + A[i];
        }
    }
}

InputArray: [3, 1, 4, 1, 5, 9]

OutputPrefix sum array: [3, 4, 8, 9, 14, 23]

Example

Run the example step by step

Output

Answering Queries

Once P is built, the sum of elements from index L to R is simply the sum up to R minus the sum up to the element just before L.

The formula is Sum(L, R) = P[R] - P[L-1]. We subtract the prefix that is not part of the requested range.

Query is a single O(1) subtraction
If L is 0, the sum is just P[R]
Zero-padding the prefix array simplifies the formula

Beyond Summation

The prefix pattern works for any mathematical operation that can be 'reversed' or 'subtracted'.

For example, prefix products (using division), prefix XORs (using XOR to reverse), or counting frequencies of characters in a string up to an index.

Works with invertible operations
Prefix XOR: XOR(L, R) = P[R] ^ P[L-1]
Does not work for Max/Min (not invertible)