Lesson 6 · 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.

Paying Once Instead of Every Time

Given an array and many queries of the form 'what is the sum of elements i through j', the direct approach loops from i to j and adds. One query costs O(n) in the worst case, so q queries cost O(n·q) — for an array of 100,000 elements and 100,000 queries, that is ten billion additions.

The observation that fixes it: those loops overlap enormously. Summing 0..500 and then 0..600 recomputes the first 501 additions a second time. Prefix sums pay for that work exactly once and then reuse it.

This is the general trade the technique represents — spend O(n) time and O(n) space up front to make each subsequent query O(1). It is only worth it when queries are repeated, and it is only valid when the underlying array does not change between them.

That second condition is the real constraint. A single update to element k invalidates every prefix from k onwards, costing O(n) to repair. An array queried many times and rarely updated is the prefix sum's case; one that is updated frequently needs a Fenwick tree or segment tree, which accept O(log n) queries in exchange for O(log n) updates.

Choosing a range-sum structure by workload
Structure	Build	Query	Update
Direct loop	—	O(n)	O(1)
Prefix sum	O(n)	O(1)	O(n)
Fenwick tree	O(n)	O(log n)	O(log n)
Segment tree	O(n)	O(log n)	O(log n)

Naive repeated queries cost O(n·q) and redo overlapping work
Prefix sums pay O(n) once, then answer in O(1)
Requires the array to stay static between queries
Frequent updates call for a Fenwick or segment tree instead

Building the Array

Define P[k] as the sum of the first k elements — that is, elements 0 through k−1. Then P[0] = 0, representing the empty prefix, and each later entry is P[k] = P[k-1] + arr[k-1]. One pass, O(n) time and O(n) extra space.

The detail that matters is the length: make P have n+1 entries, not n. That leading zero is not decoration. It is what lets a query starting at index 0 use the same formula as every other query, instead of needing an if (i == 0) branch. Almost every off-by-one bug in prefix-sum code traces back to an n-length array.

Be deliberate about which convention you are using, because both appear in textbooks. The n+1 form used here is exclusive: P[k] excludes arr[k]. The alternative, P[k] = arr[0] + … + arr[k], is inclusive and shifts every index in the query formula by one. Mixing them mid-problem is a reliable way to produce answers that are wrong by exactly one element.

If the original array is not needed afterwards, the prefix sums can be written into it in place, reducing the extra space to O(1). Note the trade: queries stay O(1), but the original values are gone and can only be recovered by subtracting neighbours.

P[0] = 0; P[k] = P[k-1] + arr[k-1]
Size the array n+1 — the leading zero removes the i = 0 branch
Fix one convention, exclusive or inclusive, and state it
In-place construction saves the space but destroys the input

What Else the Idea Covers

Nothing about the technique is specific to addition. Any associative and invertible operation works, because the query depends on being able to cancel the unwanted prefix.

Prefix XOR is the common one: since XOR is its own inverse, the XOR of a range is P[j+1] ^ P[i], with the same shape as the sum. Prefix products work in principle, but zeros destroy invertibility — one zero anywhere makes every later prefix zero and unrecoverable — so they need special handling or a different approach.

Prefix minimum and maximum do not work at all, and understanding why is the point. There is no operation that removes an element from a running minimum: knowing the minimum of 0..j and the minimum of 0..i tells you nothing about the minimum of i..j, because the smaller value may lie in the discarded part. Range minimum queries therefore need a sparse table or a segment tree, not a prefix array.

Prefix counts are a useful variant. Building prefix sums of a boolean array — 1 for elements matching a predicate, 0 otherwise — answers 'how many elements in this range satisfy the condition' in O(1), which is how range-frequency questions are handled without re-scanning.

Works for any associative, invertible operation
Prefix XOR mirrors prefix sum exactly
Min and max are not invertible — use a sparse or segment tree
Prefix counts over a 0/1 array answer range-frequency queries

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.

Implementation

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];
    }
    cout << "Prefix sum array: [";
    for (size_t i = 0; i < P.size(); i++) {
        if (i) cout << ", ";
        cout << P[i];
    }
    cout << "]\n";
}

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];
        }
        System.out.println("Prefix sum array: " + java.util.Arrays.toString(P));
    }
}

Watch it run

Step through it

Running on Array: [3, 1, 4, 1, 5, 9]

Output

Read all 14 Steps

The question a prefix sum answers We have A = [3, 1, 4, 1, 5, 9] and we will be asked for the sum of many different ranges. Summing each range directly costs O(n) every time. The prefix array pays that cost once.
P[0] = 0, the empty prefix The prefix array is one longer than A and starts with 0 — the sum of no elements. That leading zero is what removes the special case for ranges that begin at index 0.
P[1] = P[0] + A[0] 0 + 3 = 3. Each entry is the previous entry plus one element of A, so the whole array is built in a single pass.
P[2] = P[1] + A[1] 3 + 1 = 4. P[2] is now the sum of the first two elements of A.
P[3] = P[2] + A[2] 4 + 4 = 8. No inner loop has run — each step does one addition.
P[4] = P[3] + A[3] 8 + 1 = 9.
P[5] = P[4] + A[4] 9 + 5 = 14.
P[6] = P[5] + A[5] 14 + 9 = 23, the sum of the whole array. The build is finished in O(n) time and O(n) extra space.
Every entry is a sum from the start P[k] holds the sum of the first k elements of A. Nothing here is a range yet — each value is anchored at index 0.
Query: sum of A[1..3] We want 1 + 4 + 1 = 6. The naive loop would touch three elements. The prefix array will do it with one subtraction.
Subtract the two prefixes P[4] - P[1] = 9 - 3 = 6. P[4] is the sum of everything up to index 3; P[1] is the sum of everything before index 1. Subtracting cancels the shared front portion and leaves exactly the range.
Any other range costs the same Sum of A[2..5] is P[6] - P[2] = 23 - 4 = 19. A range covering the whole array is P[6] - P[0] = 23. Every range sum query is O(1) no matter how wide it is.
Why the leading zero matters A range starting at index 0 is P[j+1] - P[0] = P[j+1] - 0. Without the leading zero this case would need its own if statement. One wasted slot removes a branch from every query.
The limit of the technique All of this assumes A never changes. Update one element and every prefix after it is wrong, so the rebuild is O(n). For data that is both queried and updated, a Fenwick tree keeps both operations at O(log n).

Subarray Sums with a Hash Map

The highest-value application in interviews is not range queries at all. It is counting subarrays whose sum equals a target k, and it comes from reading the formula in the other direction.

A subarray ending at j sums to k exactly when P[j+1] − P[i] = k, which rearranges to P[i] = P[j+1] − k. So the number of subarrays ending at j with sum k is simply how many earlier prefixes equal P[j+1] − k.

That turns the problem into a single pass with a hash map from prefix value to how many times it has occurred. Maintain a running total, look up running − k to add to the count, then record the running total. O(n) time, O(n) space, with no nested loop.

The map must be seeded with {0: 1} before the loop starts. That entry represents the empty prefix and is what allows a subarray beginning at index 0 to be counted. Omitting it produces code that is correct for every case except subarrays starting at the front — a bug that passes casual testing and fails on submission.

The same rearrangement handles nearby problems: longest subarray summing to k stores the first index at which each prefix appeared rather than a count, and 'subarray sum divisible by k' keys the map on running % k instead, since two prefixes with the same remainder bracket a divisible range.

P[i] = P[j+1] − k turns counting into a lookup
One pass with a hash map: O(n) time, O(n) space
Seed the map with {0: 1} for subarrays starting at index 0
Store first-seen indices for longest-subarray variants