Free lesson · DSA Mastery - Interview Prep, End to End

Introduction to Prefix Sum

Medium7 min readdsaprefix-sum

Introduction to Prefix Sum

Prefix sum is one of those techniques that feels almost too simple to be powerful - and then you see it turn an O(n) query into O(1), or an O(n²) algorithm into O(n), and you understand why it's everywhere. The idea: precompute cumulative sums once, then answer range-sum questions instantly.

This chapter builds the mental model. The core identity, the three families of prefix-sum problems, and the signals that tell you to reach for the technique. Like two pointers, prefix sum is a building block - once you internalize it, you'll spot it inside sliding window, dynamic programming, and 2D matrix problems throughout the rest of the course.

Why Prefix Sum Matters

The motivating problem: given an array, answer many queries of the form "what is the sum of elements between index i and index j?"

The naive approach recomputes each sum by looping from i to j - O(n) per query, O(n·q) for q queries. If you have thousands of queries on a large array, that's far too slow.

Prefix sum precomputes a cumulative array once (O(n)), then answers each query in O(1) with a single subtraction. For q queries: O(n + q) instead of O(n·q). That's the whole pitch - and it generalizes far beyond simple range sums.

Three reasons the technique is interview-critical:

1. It's a primitive that composes. Subarray Sum Equals K, Continuous Subarray Sum, Range Sum Query 2D - all are prefix sum plus one more idea (a hash map, a modulo, inclusion-exclusion). Master the primitive and these become accessible.

2. It converts range questions into point questions. A range [i, j] becomes the difference of two prefix values. This reframing is the key insight that unlocks many problems.

3. It pairs beautifully with hashing. The most powerful prefix-sum problems combine the cumulative array with a hash map, achieving O(n) where brute force is O(n²). This is the same complement-lookup idea from Two Sum, applied to running sums.

The Core Identity

Define the prefix sum array P where P[k] is the sum of the first k elements:

P[0] = 0
P[k] = nums[0] + nums[1] + ... + nums[k-1]   (sum of first k elements)

So P[0] = 0 (empty prefix), P[1] = nums[0], P[2] = nums[0] + nums[1], and so on. P has length n + 1.

The fundamental identity for the sum of the subarray from index i to index j (inclusive):

sum(i, j) = P[j + 1] - P[i]

This is the entire technique in one line. The sum of any range is the difference of two prefix values. Let's see why: P[j+1] is the sum of everything up to and including index j; P[i] is the sum of everything before index i. Subtracting removes the part before i, leaving exactly nums[i] + ... + nums[j].

graph LR
    A["P[i] = sum of<br/>nums[0..i-1]"] --> B["P[j+1] = sum of<br/>nums[0..j]"]
    B --> C["sum(i,j) = P[j+1] - P[i]"]
    
    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9

This diagram shows the core prefix-sum identity. P at index i is the sum of all elements before index i. P at index j plus one is the sum of all elements up to and including index j. The sum of the range from i to j is their difference: P at j plus one minus P at i.

The Off-By-One Convention

The most common source of bugs in prefix-sum code is the indexing convention. Using the "P[0] = 0, length n + 1" convention (a leading zero) makes the range formula clean: sum(i, j) = P[j+1] - P[i], with no special cases for i = 0.

Some people use a convention where P[k] is the sum including index k (no leading zero, length n). That works too, but then sum(i, j) = P[j] - P[i-1], which needs a special case when i = 0. The leading-zero convention avoids that. We'll use it consistently.

Building the Prefix Sum Array

The construction is a single pass:

int n = nums.length;
int[] P = new int[n + 1];   // P[0] = 0 by default
for (int k = 0; k < n; k++) {
    P[k + 1] = P[k] + nums[k];
}

Each entry is the previous prefix plus the current element. O(n) time, O(n) space.

For a quick example, nums = [3, 1, 4, 1, 5]:

P[0] = 0
P[1] = 0 + 3 = 3
P[2] = 3 + 1 = 4
P[3] = 4 + 4 = 8
P[4] = 8 + 1 = 9
P[5] = 9 + 5 = 14

P = [0, 3, 4, 8, 9, 14]

Now sum(1, 3) (elements at indices 1, 2, 3 = 1, 4, 1 = 6) is P[4] - P[1] = 9 - 3 = 6. Correct, and computed in O(1).

The Three Families

Prefix-sum problems fall into three families, which map to the sub-groups in this module.

Family 1: Basic Prefix Sum

Direct application of the range-sum identity. Precompute, then answer queries or find a position based on cumulative sums. Examples: Range Sum Query, Running Sum, Find Pivot Index. These teach the mechanics.

Family 2: Prefix Sum + Hash Map

The powerhouse family. You scan the array maintaining a running prefix sum, and use a hash map of prefix sums seen so far to answer "how many subarrays end here with property P?" in O(1) per element. This is the complement-lookup pattern: to find a subarray with sum k ending at the current position, look for a previous prefix sum equal to current - k.

Examples: Subarray Sum Equals K, Subarray Sums Divisible by K, Continuous Subarray Sum, Contiguous Array. These are the most important - and the most frequently asked in interviews.

Family 3: 2D Prefix Sum

Extend the idea to matrices. A 2D prefix sum lets you compute the sum of any rectangular submatrix in O(1) using inclusion-exclusion. A related idea, the difference array, lets you apply many range updates efficiently. Examples: Range Sum Query 2D, Range Addition, Matrix Block Sum.

When to Reach for Prefix Sum

The clearest signal: you're repeatedly asked for sums (or counts) over ranges or subarrays. If a brute-force solution loops to recompute range sums, prefix sum almost certainly helps.

Other signals:

• "Sum of elements between index i and j" - directly the range identity.
• "Number of subarrays with sum equal to / divisible by / a multiple of k" - prefix sum + hash map.
• "Find a subarray (or split point) where left sum equals right sum" - prefix sum.
• "Sum of a submatrix / rectangle" - 2D prefix sum.
• "Apply many range increments, then read the final array" - difference array.

Counter-signals where prefix sum doesn't fit:

• The array changes between queries (frequent updates). A static prefix sum is invalidated by updates. For mixed updates and queries, a Fenwick tree or segment tree (Section 32) is the right tool.
• You need range min/max, not sum. Prefix sum relies on subtraction being invertible. Min and max aren't invertible, so you need a sparse table or segment tree instead.
• The "combine" operation isn't a group operation. Prefix sum works for sum (and XOR, product if no zeros) - any operation with an inverse. It doesn't work for non-invertible operations.

Prefix Sum vs. Sliding Window vs. Hashing

Three linear-scan techniques that often solve similar-looking problems:

The decision that trips people up: for "subarray with sum K" problems, use prefix sum + hash map when the array can have negative numbers; use sliding window when all numbers are positive. Sliding window relies on the sum being monotonic as the window grows - negatives break that, so prefix sum is the safe general tool.

Common Pitfalls With Prefix Sum

A few recurring issues:

Off-by-one in the index convention. Decide whether P has a leading zero (length n + 1) and stick with it. The leading-zero convention makes sum(i, j) = P[j+1] - P[i] clean. Mixing conventions mid-solution causes subtle bugs.

Integer overflow. Cumulative sums grow. For large arrays with large values, the prefix sum can exceed int range - use long when sums could be big.

Forgetting to seed the hash map. In the prefix-sum-plus-hash-map family, you must insert {0: 1} (or {0: -1} for index-based variants) before scanning, to account for subarrays that start at index 0. This is the single most common bug in this family.

Using prefix sum when the array mutates. If elements change between queries, a static prefix sum becomes stale. Recognize when you need a Fenwick/segment tree instead.

What This Section Covers

The 12 problem topics in Module 11 are organized by family:

• Basic Prefix Sum (4 topics): Range Sum Query – Immutable, Running Sum of 1d Array, Find Pivot Index, Maximum Population Year.
• Prefix Sum + Hash Map (4 topics): Subarray Sum Equals K, Subarray Sums Divisible by K, Continuous Subarray Sum, Contiguous Array.
• 2D Prefix Sum (4 topics): Range Addition, Range Sum Query 2D – Immutable, Increment Submatrices by One, Matrix Block Sum.

By the end, you'll be able to recognize the technique instantly, choose the right family, handle the off-by-one and overflow traps cleanly, and combine prefix sum with hashing for the O(n) subarray-counting problems that interviewers love.

Let's start with the foundational application: Range Sum Query – Immutable, where the technique appears in its purest form.

Back to DSA Mastery - Interview Prep, End to End