Learn Prefix Sum – Algorithm Guide

01

Introduction to Prefix Sum

The Prefix Sum is a powerful algorithmic pattern used to perform fast range queries on an array. By precomputing cumulative sums, we can answer queries about the sum of elements in any continuous subarray in O(1) time instead of O(N).

What is a Prefix Sum Array?

Given an array A of size N, its prefix sum array P is also of size N (or N+1 for convenience). Each element at index i in the prefix sum array stores the sum of all elements in the original array from index 0 to i.

P[i] = A[0] + A[1] + ... + A[i]

Index	0	1	2	3	4
Original Array (A)	2	4	6	8	10
Prefix Sum (P)	2	6	12	20	30

Practice: Introduction

If the original array is [1, 3, 5, 7], what is the prefix sum array?

Answer: [1, 4, 9, 16]

Explanation: P[0] = 1. P[1] = 1 + 3 = 4. P[2] = 1 + 3 + 5 = 9. P[3] = 1 + 3 + 5 + 7 = 16.

02

Construction Process

Building a prefix sum array is straightforward and requires only a single pass through the array. This takes O(N) time and O(N) space.

The Algorithm

Initialize an array P of the same size as A.
Set P[0] = A[0].
For each index i from 1 to N-1, set P[i] = P[i-1] + A[i].

Python

def build_prefix_sum(arr):
    n = len(arr)
    if n == 0: return []
    
    prefix = [0] * n
    prefix[0] = arr[0]
    
    for i in range(1, n):
        prefix[i] = prefix[i-1] + arr[i]
        
    return prefix

💡

Often, it's convenient to make the prefix sum array size N+1 and set P[0] = 0. This avoids out-of-bounds errors when querying sums that start from index 0.

03

Range Query Examples

Once the prefix sum array is built, finding the sum of elements between any two indices L and R (inclusive) is a simple subtraction operation.

The Formula

To find the sum of A[L...R]:

If L == 0, the sum is just P[R].
If L > 0, the sum is P[R] - P[L-1].

JavaScript

function rangeQuery(prefix, L, R) {
  if (L === 0) return prefix[R];
  return prefix[R] - prefix[L - 1];
}

Practice: Range Query

Given P = [1, 4, 9, 16], what is the sum of elements from index 1 to 2 inclusive?

Answer: 8

Explanation: Sum from L=1 to R=2 is P[2] - P[0] = 9 - 1 = 8. (The original array is [1, 3, 5, 7], and A[1]+A[2] = 3+5 = 8).

04

Applications

Prefix sums are foundational and appear in numerous optimization problems.

1. Equilibrium Index

An equilibrium index is an index where the sum of elements to its left equals the sum to its right. We can find this efficiently using prefix sums.

2. Difference Arrays

If you need to perform many range additions (e.g., "Add 5 to all elements from L to R"), a difference array is the inverse of a prefix sum array and can perform this update in O(1) time.

3. 2D Prefix Sums

For a 2D matrix, a 2D prefix sum array allows finding the sum of elements within any rectangular sub-grid in O(1) time. The formula becomes: S = P[r2][c2] - P[r1-1][c2] - P[r2][c1-1] + P[r1-1][c1-1]

05

Practice Exercises

Test your understanding of the prefix sum technique.

Exercise 1: Finding Equilibrium

Given the array [-7, 1, 5, 2, -4, 3, 0], what is the equilibrium index? (Use the prefix sum approach).

Answer: Index 3

Explanation: At index 3 (value is 2), the sum of elements to the left is -7 + 1 + 5 = -1. The sum to the right is -4 + 3 + 0 = -1. Since both sides equal -1, index 3 is an equilibrium index.

Exercise 2: Time Complexity

If you have an array of N elements and need to answer Q range queries, what is the time complexity of using the prefix sum method versus calculating the sum directly each time?

Answer: O(N + Q) vs O(Q * N)

Explanation: Prefix sum takes O(N) to build and O(1) per query, leading to O(N + Q). Direct calculation takes O(N) per query, leading to O(Q * N).

Algo Infinity Verse

Master the Prefix Sum Pattern Efficient Range Queries in O(1) Time

➕ Learn Prefix Sum