What Is a Prefix Sum? Build Once, Query Any Range in O(1)

You have an array of a million numbers. Someone asks for the sum of elements from index 200 to index 800,000. Easy. You loop through those 800,000 elements and add them up. Then they ask again. And again. Ten thousand times. Your server starts sweating. Your users stop waiting. Your interviewer closes their laptop.

A prefix sum turns that problem inside out. You spend O(n) once, upfront, to build a running total. Every range query after that costs exactly O(1). No loops. No revisiting old ground. One subtraction and you're done.

Walk Through the Idea Before Writing Any Code

Start with this array:

arr = [3, 1, 4, 1, 5, 9, 2, 6]
       0  1  2  3  4  5  6  7

The prefix sum array adds a leading zero and builds up running totals:

prefix = [0, 3, 4, 8, 9, 14, 23, 25, 31]
          0  1  2  3  4   5   6   7   8

prefix[i] holds the sum of the first i elements. prefix[0] is 0 by definition. prefix[1] is 3. prefix[3] is 3+1+4 = 8.

The leading zero is not optional. It is what makes the formula work for every range, including ranges that start at index 0. Skip it and you'll be writing special-case code at 2am wondering why your solution is wrong on exactly the inputs that start at the beginning.

One Subtraction Gets You Any Range

Want the sum of arr[l..r] (inclusive, 0-indexed)? One subtraction:

sum(l, r) = prefix[r + 1] - prefix[l]

Check it. Sum of arr[2..5] (elements 4, 1, 5, 9):

prefix[6] - prefix[2] = 23 - 4 = 19

4 + 1 + 5 + 9 = 19. Correct.

prefix[r+1] is the sum of all elements from index 0 through r. prefix[l] is the sum from 0 through l-1. Subtract the prefix and everything before index l cancels. What remains is exactly arr[l] + arr[l+1] + ... + arr[r].

How You Build a Prefix Sum Array

def build_prefix(arr):
    prefix = [0] * (len(arr) + 1)
    for i in range(len(arr)):
        prefix[i + 1] = prefix[i] + arr[i]
    return prefix

One pass, O(n) time, O(n) space. After that, every query is:

def range_sum(prefix, l, r):
    return prefix[r + 1] - prefix[l]

Pay Once, Query Forever

Operation	Without Prefix Sum	With Prefix Sum
Build	O(1)	O(n)
Single range query	O(n)	O(1)
k range queries	O(k × n)	O(n + k)

The tradeoff is upfront work for constant-time queries. One query? Prefix sum is overkill. A thousand queries? It's not even a contest. The crossover happens almost immediately.

Space is O(n) for the prefix array. The original array can be discarded after building if you don't need it.

How This Shows Up in Interviews

Pattern 1: The Layup

LeetCode 303 (Range Sum Query, Immutable) is the canonical example. Build the prefix array in the constructor, answer each query in O(1). Interviewers use it to see whether you think about preprocessing at all. Once you know the idea, this one writes itself.

Pattern 2: The Trick That Needs a Trick

LeetCode 560 (Subarray Sum Equals K) asks: how many contiguous subarrays sum to exactly k?

The naive approach checks every pair (i, j) in O(n²). Every candidate writes that solution. With prefix sums and a hash map, you do it in O(n), which is the solution that gets you to the next round.

The key insight: if prefix[j] - prefix[i] = k, then the subarray from index i to j-1 sums to k. Rearrange: you need prefix[i] = prefix[j] - k.

def subarray_sum(nums, k):
    count = 0
    total = 0
    seen = {0: 1}  # the empty prefix
    for num in nums:
        total += num
        count += seen.get(total - k, 0)
        seen[total] = seen.get(total, 0) + 1
    return count

The {0: 1} initialization handles subarrays that start at index 0. Without it, you silently undercount, pass every positive test case, and fail the first real one. Classic.

This combination handles negative numbers and zeros, which sliding window cannot. If the problem involves subarray sums and has no restriction to positive numbers, this is the pattern.

See prefix sum problems explained for a full breakdown of the signal patterns that tell you when to reach for this.

Pattern 3: 2D Prefix Sums

The same idea extends to matrices. For a matrix where you need the sum of any rectangular subregion, build a 2D prefix array:

def build_2d_prefix(matrix):
    m, n = len(matrix), len(matrix[0])
    prefix = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m):
        for j in range(n):
            prefix[i+1][j+1] = (
                prefix[i][j+1]
                + prefix[i+1][j]
                - prefix[i][j]
                + matrix[i][j]
            )
    return prefix

Query a rectangle from (r1, c1) to (r2, c2):

def rect_sum(prefix, r1, c1, r2, c2):
    return (
        prefix[r2+1][c2+1]
        - prefix[r1][c2+1]
        - prefix[r2+1][c1]
        + prefix[r1][c1]
    )

The addition at the end corrects for double-counting the top-left rectangle. Inclusion-exclusion in two dimensions. It looks more intimidating than it is. Draw a picture once, convince yourself it works, and then never think about it again.

Build: O(m×n). Each query: O(1).

The Off-By-One Trap (It Gets Everyone Once)

The single most common mistake is forgetting the leading zero and writing prefix[i] = sum of arr[0..i] instead of prefix[i+1] = sum of arr[0..i].

When you do that, the range formula becomes prefix[r] - prefix[l-1], which blows up when l = 0 because prefix[-1] doesn't exist. In Python, prefix[-1] silently returns the last element, which is not what you want. You will be confused for longer than you'd like to admit.

Always pad with the leading zero. It costs nothing and eliminates an entire class of bugs.

Four Ways to Still Mess This Up

Modifying the array in place. Some implementations accumulate directly into the original array. This works, right up until you need the original values and they're gone. Keep the prefix array separate unless you can prove you never need the originals.

Forgetting {0: 1} in the hash map variant. This silently undercounts subarrays that start at index 0. Your code will look correct. Your tests will mostly pass. The edge cases will not.

Using prefix sums when sliding window is enough. If all values are positive and you need subarrays summing to at most k, a sliding window does it with O(1) space. See the sliding window guide for when to choose between them. Reaching for a bigger hammer than you need is its own category of mistake.

Querying outside bounds. prefix[r+1] will happily go out of bounds if you don't validate your query indices. Validate before querying.

One Structure, Every Language

# Python 3
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]

# Python 2
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]

// JavaScript
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];
}

// TypeScript
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];
}

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

int rangeSum(int[] prefix, int l, int r) {
    return prefix[r + 1] - prefix[l];
}

// C++
vector<int> buildPrefix(const vector<int>& arr) {
    vector<int> prefix(arr.size() + 1, 0);
    for (int i = 0; i < (int)arr.size(); i++) {
        prefix[i + 1] = prefix[i] + arr[i];
    }
    return prefix;
}

int rangeSum(const vector<int>& prefix, int l, int r) {
    return prefix[r + 1] - prefix[l];
}

// C
void buildPrefix(int *arr, int n, int *prefix) {
    prefix[0] = 0;
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + arr[i];
    }
}

int rangeSum(int *prefix, int l, int r) {
    return prefix[r + 1] - prefix[l];
}

// Go
func buildPrefix(arr []int) []int {
    prefix := make([]int, len(arr)+1)
    for i, val := range arr {
        prefix[i+1] = prefix[i] + val
    }
    return prefix
}

func rangeSum(prefix []int, l, r int) int {
    return prefix[r+1] - prefix[l]
}

// Rust
fn build_prefix(arr: &[i64]) -> Vec<i64> {
    let mut prefix = vec![0i64; arr.len() + 1];
    for (i, &val) in arr.iter().enumerate() {
        prefix[i + 1] = prefix[i] + val;
    }
    prefix
}

fn range_sum(prefix: &[i64], l: usize, r: usize) -> i64 {
    prefix[r + 1] - prefix[l]
}

// Swift
func buildPrefix(_ arr: [Int]) -> [Int] {
    var prefix = [Int](repeating: 0, count: arr.count + 1)
    for i in 0..<arr.count {
        prefix[i + 1] = prefix[i] + arr[i]
    }
    return prefix
}

func rangeSum(_ prefix: [Int], _ l: Int, _ r: Int) -> Int {
    return prefix[r + 1] - prefix[l]
}

// Kotlin
fun buildPrefix(arr: IntArray): IntArray {
    val prefix = IntArray(arr.size + 1)
    for (i in arr.indices) {
        prefix[i + 1] = prefix[i] + arr[i]
    }
    return prefix
}

fun rangeSum(prefix: IntArray, l: Int, r: Int): Int {
    return prefix[r + 1] - prefix[l]
}

// C#
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;
}

int RangeSum(int[] prefix, int l, int r) {
    return prefix[r + 1] - prefix[l];
}

# Ruby
def build_prefix(arr)
  prefix = [0]
  arr.each { |val| prefix << prefix.last + val }
  prefix
end

def range_sum(prefix, l, r)
  prefix[r + 1] - prefix[l]
end

// PHP
function buildPrefix(array $arr): array {
    $prefix = [0];
    foreach ($arr as $val) {
        $prefix[] = end($prefix) + $val;
    }
    return $prefix;
}

function rangeSum(array $prefix, int $l, int $r): int {
    return $prefix[$r + 1] - $prefix[$l];
}

When to Actually Reach for This

A prefix sum fits when you see these signals together:

• The array is fixed (immutable or rarely updated)
• Multiple queries ask for aggregate values over subarrays
• The brute-force nested loop is O(n) per query and the constraint makes that too slow

If you need updates between queries, a prefix sum breaks because rebuilding costs O(n) every time. That defeats the whole point. Reach for a Fenwick tree instead, which handles both point updates and range queries in O(log n) and lets you update without starting over.

For a curated list of problems to practice, see the top prefix sum LeetCode problems.

If you want to test whether you can recognize and explain this pattern under pressure, SpaceComplexity puts you in a voice-based mock interview and scores how clearly you narrate the reasoning as you build toward the solution.

Further Reading

• Prefix Sum - USACO Guide
• Prefix Sum Array - GeeksforGeeks
• LeetCode 303: Range Sum Query - Immutable
• LeetCode 560: Subarray Sum Equals K
• LeetCode 304: Range Sum Query 2D - Immutable
• Prefix Sums - Wikipedia