PATTERN 4 OF 22

Prefix Sums

Precompute cumulative sums to answer range sum queries in O(1) time, and combine with hash maps to count subarrays with a given sum in a single pass.

Time: O(n) build, O(1) query

Space: O(n)

Learn & Reference

Understanding the Pattern

Prefix Sum Pattern

The prefix sum pattern converts expensive repeated range queries into O(1) lookups by precomputing cumulative sums. Instead of summing elements from scratch for every query, you build a prefix array once in O(n) and answer any range sum in constant time using subtraction.

Core Concept

A prefix sum array prefix is defined as:

prefix[0] = 0 (empty prefix)
prefix[i] = arr[0] + arr[1] + ... + arr[i-1]

The sum of any subarray arr[left..right] (inclusive) is:

sum(left, right) = prefix[right + 1] - prefix[left]

This works because prefix[right + 1] contains the sum of everything up to index right, and subtracting prefix[left] removes the elements before left.

The 3 Prefix Sum Archetypes

1. Build & Query (Range Sum)

Build a prefix array and answer multiple range sum queries in O(1) each. This is the foundation of the pattern and appears directly in problems like "Range Sum Query - Immutable".

2. Prefix Sum + Hash Map (Subarray Sum = k)

The most common interview variant. Instead of building a full prefix array, maintain a running prefix sum and a hash map of {prefix_value: count}. At each index, check if prefix - k exists in the map. This counts all subarrays ending at the current index with sum equal to k.

Why it works: If at index j the prefix sum is P, and at some earlier index i the prefix sum was P - k, then the subarray arr[i+1..j] has sum exactly k. The hash map tracks how many earlier indices had each prefix value.

Key insight: Initialize the map with {0: 1} to handle subarrays starting from index 0.

3. Prefix XOR / Prefix Product

The same principle applies to XOR and multiplication. For XOR, xor(left, right) = prefix[right + 1] ^ prefix[left]. For products, use a prefix product array (watch for zeros).

2D Prefix Sums

For matrix range sum queries, build a 2D prefix sum where each cell contains the sum of the rectangle from (0,0) to (i,j). Any sub-rectangle sum can be computed in O(1) using inclusion-exclusion:

sum(r1,c1,r2,c2) = prefix[r2+1][c2+1] - prefix[r1][c2+1]
                   - prefix[r2+1][c1] + prefix[r1][c1]

When Prefix Sum Fails

When the array is frequently modified (use a Fenwick tree or segment tree instead)
When you need minimum/maximum over a range (use sparse table or segment tree)
When the subarray condition is not based on sum (e.g., longest subarray with all distinct elements — use sliding window)
When the problem requires non-contiguous subsequences (use dynamic programming)

Common Mistakes

Off-by-one in prefix indexing: The prefix array has length n + 1, with prefix[0] = 0. The sum of arr[left..right] is prefix[right + 1] - prefix[left], not prefix[right] - prefix[left - 1]
Forgetting to initialize hash map with {0: 1}: Without this, subarrays starting from index 0 are missed entirely
Modifying prefix values after building: The prefix array is read-only after construction. If the original array changes, the entire prefix must be rebuilt
Integer overflow on large sums: Prefix sums can grow very large. Use long in Java or be aware of overflow in languages without arbitrary precision
Confusing prefix sum + hash map with sliding window: Prefix sum works when elements can be negative (sliding window does not). If the problem says "positive integers only" and asks for subarray length, consider sliding window instead

When to Use

Sum of elements between index i and j

Number of subarrays with sum equal to k

Subarray sum divisible by k

Multiple range sum queries on a static array

Find a contiguous subarray with sum = target (especially with negative numbers)

Matrix region sum queries

XOR of a subarray

Prefix product / running product problems

Problems where brute force sums subarrays in O(n) per query

Count subarrays where sum satisfies condition X

Template

1# --- Build Prefix Sum Array ---
2def build_prefix(nums):
3    """Build prefix sum array where prefix[i] = sum(nums[0..i-1])"""
4    n = len(nums)
5    prefix = [0] * (n + 1)
6    for i in range(n):
7        prefix[i + 1] = prefix[i] + nums[i]
8    return prefix
9
10# --- Range Sum Query ---
11def range_sum(prefix, left, right):
12    """Sum of nums[left..right] inclusive, O(1)"""
13    return prefix[right + 1] - prefix[left]
14
15# --- Subarray Sum Equals K (Prefix + Hash Map) ---
16def subarray_sum(nums, k):
17    """Count subarrays with sum exactly k"""
18    count = 0
19    prefix = 0
20    seen = {0: 1}  # prefix_sum -> count
21
22    for num in nums:
23        prefix += num
24        # If (prefix - k) was seen before, those subarrays sum to k
25        if prefix - k in seen:
26            count += seen[prefix - k]
27        seen[prefix] = seen.get(prefix, 0) + 1
28
29    return count

{ }

Syntax Reference

1# === Build Prefix Sum Array ===
2nums = [1, 2, 3, 4, 5]
3prefix = [0] * (len(nums) + 1)
4for i in range(len(nums)):
5    prefix[i + 1] = prefix[i] + nums[i]
6# prefix = [0, 1, 3, 6, 10, 15]
7
8# === Range Sum Query (inclusive) ===
9def range_sum(prefix, left, right):
10    return prefix[right + 1] - prefix[left]
11
12# range_sum(prefix, 1, 3) = prefix[4] - prefix[1] = 10 - 1 = 9
13
14# === Using itertools.accumulate ===
15from itertools import accumulate
16prefix = [0] + list(accumulate(nums))
17
18# === Prefix Sum + Hash Map ===
19from collections import defaultdict
20prefix = 0
21seen = defaultdict(int)
22seen[0] = 1
23for num in nums:
24    prefix += num
25    if prefix - k in seen:
26        count += seen[prefix - k]
27    seen[prefix] += 1

📋

Common Recipes

1# --- Range Sum Query ---
2def build_prefix(nums):
3    prefix = [0] * (len(nums) + 1)
4    for i in range(len(nums)):
5        prefix[i + 1] = prefix[i] + nums[i]
6    return prefix
7
8def range_sum(prefix, left, right):
9    return prefix[right + 1] - prefix[left]
10
11# --- Subarray Sum Equals K ---
12def subarray_sum(nums, k):
13    count, prefix = 0, 0
14    seen = {0: 1}
15    for num in nums:
16        prefix += num
17        if prefix - k in seen:
18            count += seen[prefix - k]
19        seen[prefix] = seen.get(prefix, 0) + 1
20    return count
21
22# --- Prefix Product (with zero handling) ---
23def product_except_self(nums):
24    n = len(nums)
25    result = [1] * n
26    # Left prefix products
27    left = 1
28    for i in range(n):
29        result[i] = left
30        left *= nums[i]
31    # Right prefix products
32    right = 1
33    for i in range(n - 1, -1, -1):
34        result[i] *= right
35        right *= nums[i]
36    return result

O(n)

Complexity

Operation	Time	Space
Build prefix array	O(n)	O(n)
Range sum query	O(1)	O(1)
Subarray sum = k (hash map)	O(n)	O(n)
2D prefix sum build	O(m * n)	O(m * n)
2D range sum query	O(1)	O(1)

Watch Out

✗When the array is frequently modified (use a Fenwick tree or segment tree instead)
✗When you need minimum/maximum over a range (use sparse table or segment tree)
✗When the subarray condition is not based on sum (e.g., longest subarray with all distinct elements — use sliding window)
✗When the problem requires non-contiguous subsequences (use dynamic programming)
✗Off-by-one in prefix indexing: The prefix array has length `n + 1`, with `prefix[0] = 0`. The sum of `arr[left..right]` is `prefix[right + 1] - prefix[left]`, not `prefix[right] - prefix[left - 1]`
✗Forgetting to initialize hash map with {0: 1}: Without this, subarrays starting from index 0 are missed entirely
✗Modifying prefix values after building: The prefix array is read-only after construction. If the original array changes, the entire prefix must be rebuilt
✗Integer overflow on large sums: Prefix sums can grow very large. Use `long` in Java or be aware of overflow in languages without arbitrary precision
✗Confusing prefix sum + hash map with sliding window: Prefix sum works when elements can be negative (sliding window does not). If the problem says "positive integers only" and asks for subarray length, consider sliding window instead

PRACTICE PROBLEMS

Sliding Window

Binary Search