Quick Reference O(n) build, O(1) query / O(n)

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

func buildPrefix(arr []int) []int {
    prefix := make([]int, len(arr)+1)
    for i := 0; i < len(arr); i++ {
        prefix[i+1] = prefix[i] + arr[i]
    }
    return prefix
}
func rangeSum(prefix []int, l, r int) int {
    return prefix[r+1] - prefix[l]
}

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

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

fn build_prefix(arr: &[i32]) -> Vec<i32> {
    let mut prefix = vec![0; arr.len() + 1];
    for i in 0..arr.len() {
        prefix[i + 1] = prefix[i] + arr[i];
    }
    prefix
}
fn range_sum(prefix: &[i32], l: usize, r: usize) -> i32 {
    prefix[r + 1] - prefix[l]
}

function buildPrefix(arr: number[]): number[] {
    const prefix = [0];
    for (let i = 0; i < arr.length; i++) {
        prefix.push(prefix[i] + arr[i]);
    }
    return prefix;
}
function rangeSum(prefix: number[], l: number, r: number): number {
    return prefix[r + 1] - prefix[l];
}

Use when

Range sum queries
Subarray sum equals K
Count subarrays with given sum
Difference array for range updates

Watch out

Off-by-one in prefix indexing
Forgetting prefix[0] = 0
Not using hash map for subarray sum problems

Pattern

Prefix Sum

Precompute cumulative sums to answer range queries in O(1) time.

Step 01

What Is This Pattern?

The prefix sum pattern transforms an array into a cumulative sum array, where each element stores the total of all elements from the beginning up to that index. Once built, any range sum query becomes a single subtraction instead of a loop.

The Core Idea

Build a prefix array where prefix[i] = sum of elements from index 0 to i. Then any range sum [l, r] = prefix[r] - prefix[l-1].

original

0 1 2 3 4 5

| | | | | |

prefix

0 1 2 3 4 5

          sum(2..4) = 
          prefix[4]
           - 
          prefix[1]
           = 
          15
           - 
          3
           = 
          12
        

💡

Think of it like odometer readings. To find the distance between two points, you subtract the starting reading from the ending reading. Prefix sums work the same way: subtract the cumulative sum at the start from the cumulative sum at the end.

Step 02

When to Use It

Look for these signals in a problem:

Recognition Signals

Multiple range sum queries on a static array

If you need to answer many "sum from i to j" queries, brute force is O(n) per query. Prefix sums make each query O(1).

"Sum of subarray" problems

Any time the problem involves summing contiguous elements, prefix sums can often optimize the brute-force approach.

Finding subarrays with a given sum

"Count subarrays with sum = k" or "longest subarray with sum = k" often require the HashMap variant.

2D range queries

Sum of a submatrix can be computed in O(1) with a 2D prefix sum using inclusion-exclusion.

Step 03

Building the Prefix Sum

Each cell in the prefix array accumulates the running total. The formula is simple: prefix[i] = prefix[i-1] + nums[i]. Let's watch it build step by step from [1, 2, 3, 4, 5, 6].

Step-by-Step Construction

i = 0: prefix[0] = nums[0] = 1

nums

prefix

i = 1: prefix[1] = prefix[0] + nums[1] = 1 + 2 = 3

nums

prefix

i = 2: prefix[2] = prefix[1] + nums[2] = 3 + 3 = 6

nums

prefix

i = 3..5: continuing the pattern...

nums

prefix

⚡

Practical tip: Use a prefix array of size n + 1 with prefix[0] = 0. This eliminates the edge case when the range starts at index 0, since prefix[r+1] - prefix[l] always works without special checks.

Step 04

Answering Range Queries

Let's query the sum of elements from index 2 to 4 in our array [1, 2, 3, 4, 5, 6]. Using the size n+1 prefix array convention:

Query: sum(2, 4)

Using prefix[0] = 0 convention: rangeSum = prefix[r+1] - prefix[l]

nums

0 1 2 3 4 5

prefix

0 1 2 3 4 5 6

          prefix[r+1] - prefix[l] = prefix[4+1] - prefix[2] = 15 - 3 = 12
        

Verify: 3 + 4 + 5 = 12. No loop needed, just one subtraction.

Step 05

Variant: Prefix Sum with HashMap

For problems like "count subarrays with sum = k", we combine prefix sums with a HashMap. The key insight: if prefix[j] - prefix[i] = k, then the subarray from i+1 to j sums to k.

Why This Works

As we scan left to right computing the running sum, at each position j we ask: "Have I seen a prefix sum equal to currentSum - k before?" If yes, the subarray between that earlier position and j has sum exactly k.

The HashMap stores how many times each prefix sum has occurred, so we count all valid starting points in O(1).

Visual Walkthrough: nums = [1, 2, 3, -2, 5], k = 6

INDEX	NUM	SUM	SUM-K	IN MAP?	COUNT
init	-	0	-	-	0
0	1	1	-5	no	0
1	2	3	-3	no	0
2	3	6	0	YES (1x)	1
3	-2	4	-2	no	1
4	5	9	3	YES (1x)	2

Found 2 subarrays with sum = 6: [1,2,3] and [3,-2,5].

HashMap Variant Template

// Subarray sum equals k (with HashMap)
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);              // empty prefix has sum 0
int sum = 0, count = 0;

for (int num : nums) {
    sum += num;                // running prefix sum
    // How many earlier prefixes had sum = (sum - k)?
    count += map.getOrDefault(sum - k, 0);
    // Record this prefix sum
    map.merge(sum, 1, Integer::sum);
}

// Subarray sum equals k (with HashMap)
counts := make(map[int]int)
counts[0] = 1              // empty prefix has sum 0
sum, count := 0, 0

for _, num := range nums {
    sum += num                 // running prefix sum
    // How many earlier prefixes had sum = (sum - k)?
    count += counts[sum-k]
    // Record this prefix sum
    counts[sum]++
}

# Subarray sum equals k (with HashMap)
counts: dict[int, int] = {0: 1}  # empty prefix has sum 0
total = 0
count = 0

for num in nums:
    total += num               # running prefix sum
    # How many earlier prefixes had sum = (total - k)?
    count += counts.get(total - k, 0)
    # Record this prefix sum
    counts[total] = counts.get(total, 0) + 1

// Subarray sum equals k (with HashMap)
let mut counts = std::collections::HashMap::<i64, i64>::new();
counts.insert(0, 1);         // empty prefix has sum 0
let (mut sum, mut count): (i64, i64) = (0, 0);

for &num in nums {
    sum += num as i64;         // running prefix sum
    // How many earlier prefixes had sum = (sum - k)?
    count += counts.get(&(sum - k as i64)).copied().unwrap_or(0);
    // Record this prefix sum
    *counts.entry(sum).or_insert(0) += 1;
}

// Subarray sum equals k (with HashMap)
const map = new Map<number, number>();
map.set(0, 1);              // empty prefix has sum 0
let sum = 0, count = 0;

for (const num of nums) {
    sum += num;                // running prefix sum
    // How many earlier prefixes had sum = (sum - k)?
    count += map.get(sum - k) ?? 0;
    // Record this prefix sum
    map.set(sum, (map.get(sum) ?? 0) + 1);
}

🎯

Why put(0, 1)? We initialize the map with sum 0 having count 1. This handles the case where a subarray starting from index 0 has sum exactly k. Without this, we would miss those subarrays.

Step 06

Variant: 2D Prefix Sum

For matrix problems, extend the pattern to two dimensions. Each cell prefix[i][j] stores the sum of the submatrix from (0,0) to (i,j).

Inclusion-Exclusion Formula

BUILD

            prefix[i][j] =

              matrix[i][j]

              + prefix[i-1][j]

              + prefix[i][j-1]

              - prefix[i-1][j-1]

QUERY (r1,c1) to (r2,c2)

            sum =

              prefix[r2][c2]

              - prefix[r1-1][c2]

              - prefix[r2][c1-1]

              + prefix[r1-1][c1-1]

The red term corrects for the double subtraction of the overlapping rectangle. This is the classic inclusion-exclusion principle.

Step 07

Template Code

Here is the complete annotated template covering both the basic prefix sum and the HashMap variant.

Basic Prefix Sum + Range Query

// Build prefix sum (size n+1, prefix[0] = 0 for cleaner math)
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + nums[i];
}

// Range sum query [l, r] inclusive  —  O(1)
int rangeSum = prefix[r + 1] - prefix[l];

// Build prefix sum (size n+1, prefix[0] = 0 for cleaner math)
n := len(nums)
prefix := make([]int, n+1)
for i := 0; i < n; i++ {
    prefix[i+1] = prefix[i] + nums[i]
}

// Range sum query [l, r] inclusive  —  O(1)
rangeSum := prefix[r+1] - prefix[l]

# Build prefix sum (size n+1, prefix[0] = 0 for cleaner math)
prefix = [0] * (n + 1)
for i in range(n):
    prefix[i + 1] = prefix[i] + nums[i]

# Range sum query [l, r] inclusive  —  O(1)
range_sum = prefix[r + 1] - prefix[l]

// Build prefix sum (size n+1, prefix[0] = 0 for cleaner math)
let n = nums.len();
let mut prefix = vec![0i64; n + 1];
for i in 0..n {
    prefix[i + 1] = prefix[i] + nums[i] as i64;
}

// Range sum query [l, r] inclusive  —  O(1)
let range_sum = prefix[r + 1] - prefix[l];

// Build prefix sum (size n+1, prefix[0] = 0 for cleaner math)
const prefix = new Array<number>(n + 1).fill(0);
for (let i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + nums[i];
}

// Range sum query [l, r] inclusive  —  O(1)
const rangeSum = prefix[r + 1] - prefix[l];

Subarray Sum Equals K (HashMap Variant)

Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);                  // base case: empty prefix
int sum = 0, count = 0;

for (int num : nums) {
    sum += num;                    // running prefix sum
    count += map.getOrDefault(sum - k, 0);
    map.merge(sum, 1, Integer::sum);
}
return count;

func subarraySum(nums []int, k int) int {
    counts := make(map[int]int)
    counts[0] = 1                // base case: empty prefix
    sum, count := 0, 0

    for _, num := range nums {
        sum += num                 // running prefix sum
        count += counts[sum-k]
        counts[sum]++
    }
    return count
}

counts: dict[int, int] = {0: 1}  # base case: empty prefix
total = 0
count = 0

for num in nums:
    total += num                   # running prefix sum
    count += counts.get(total - k, 0)
    counts[total] = counts.get(total, 0) + 1
return count

impl Solution {
    pub fn subarray_sum(nums: Vec<i32>, k: i32) -> i32 {
        let mut counts = std::collections::HashMap::<i64, i64>::new();
        counts.insert(0, 1);       // base case: empty prefix
        let (mut sum, mut count): (i64, i64) = (0, 0);

        for &num in &nums {
            sum += num as i64;     // running prefix sum
            count += counts.get(&(sum - k as i64)).copied().unwrap_or(0);
            *counts.entry(sum).or_insert(0) += 1;
        }
        count as i32
    }
}

const map = new Map<number, number>();
map.set(0, 1);                  // base case: empty prefix
let sum = 0, count = 0;

for (const num of nums) {
    sum += num;                    // running prefix sum
    count += map.get(sum - k) ?? 0;
    map.set(sum, (map.get(sum) ?? 0) + 1);
}
return count;

Step 08

Common Problems

Practice these problems in order, from the basic range query to more creative applications:

#303 Range Sum Query - Immutable Easy

#304 Range Sum Query 2D - Immutable Medium

#560 Subarray Sum Equals K Medium

#238 Product of Array Except Self Medium

#525 Contiguous Array Medium

📝

#525 Contiguous Array is a clever twist: treat 0 as -1, then "equal number of 0s and 1s" becomes "subarray sum = 0." This transforms a counting problem into a prefix sum + HashMap problem.

Step 09

Interactive Demo

Enter an array, build the prefix sum step by step, then query any range instantly.

⚙ Prefix Sum Visualizer

Array

Step 10

Complexity Analysis

Build

O(n)

Query

O(1)

Space

O(n)

Building the prefix array requires a single pass through the input. After that, each range query is a constant-time subtraction. The trade-off is O(n) extra space for the prefix array.

Comparison with Brute Force

APPROACH	BUILD	PER QUERY	Q QUERIES
Brute Force	-	O(n)	O(n * Q)
Prefix Sum	O(n)	O(1)	O(n + Q)

⚡

When Q queries is large (say Q = 100,000 on an array of n = 100,000), brute force does 10 billion operations while prefix sum does just 200,000. That is the difference between TLE and accepted.

Step 11

Key Takeaways

1 Prefix sum trades space for speed. Pay O(n) space once, get O(1) range queries forever.
2 Use size n+1 with prefix[0] = 0. This eliminates boundary checks and makes the formula prefix[r+1] - prefix[l] work universally.
3 HashMap variant unlocks "sum equals k" problems. Store prefix sums as you go and look up currentSum - k for O(n) total time.
4 Always initialize the map with {0: 1}. Forgetting this is the most common bug. It handles subarrays that start at index 0.
5 Extends to 2D. The same idea works for matrices via inclusion-exclusion, enabling O(1) submatrix sum queries.
6 Look for creative transformations. Problems like #525 (Contiguous Array) and #238 (Product Except Self) use prefix logic with a twist. The pattern is more versatile than it first appears.

Prefix Sum

Roadmap

What Is This Pattern?

The Core Idea

When to Use It

Recognition Signals

Building the Prefix Sum

Step-by-Step Construction

Answering Range Queries

Query: sum(2, 4)

Variant: Prefix Sum with HashMap

Why This Works

Visual Walkthrough: nums = [1, 2, 3, -2, 5], k = 6

HashMap Variant Template

Variant: 2D Prefix Sum

Inclusion-Exclusion Formula

Template Code

Basic Prefix Sum + Range Query

Subarray Sum Equals K (HashMap Variant)

Common Problems

Interactive Demo

⚙ Prefix Sum Visualizer

🔍 Range Query

Complexity Analysis

Comparison with Brute Force

Key Takeaways