Prefix Sum Patterns 2026 — Complete Guide

A prefix sum is a precomputed array where each element stores the cumulative sum of the original array up to that index. Once built, any range sum query can be answered in O(1) time instead of O(n), making it one of the most powerful preprocessing techniques in competitive programming.

The key formula: prefix[i] = sum(arr[0..i-1]), using 1-indexed conventions so that prefix[0] = 0. A range sum from index l to r (inclusive) is then computed as prefix[r+1] - prefix[l]. This avoids off-by-one errors and eliminates the need for boundary checks in most implementations.

Prefix sums are the foundation for dozens of LeetCode problems across multiple difficulty levels. Understanding the core idea — precompute once, query in O(1) — unlocks five distinct pattern families: 1D range queries, 2D region sums, prefix XOR, hashmap subarray counting, and difference arrays.

The standard 1D prefix sum uses a 1-indexed array of length n+1 where prefix[0] = 0. Build phase: for i in range(1, n+1): prefix[i] = prefix[i-1] + arr[i-1]. Query phase: rangeSum(l, r) = prefix[r+1] - prefix[l] for 0-indexed l and r. The extra slot at index 0 eliminates all boundary special-casing.

LeetCode 303 (Range Sum Query Immutable) is the canonical application — the NumArray class stores the prefix array in its constructor and returns prefix[right+1] - prefix[left] for each sumRange query. LeetCode 724 (Find Pivot Index) uses prefix sums to check whether leftSum equals totalSum - leftSum - arr[i] for each candidate pivot index i.

Use 1D prefix sum whenever the problem asks for repeated range sum queries on a static array, or when you need to count subarrays with a specific sum property. The O(n) build cost pays off immediately with any two or more queries.

The hashmap variant extends prefix sums to count subarrays with a specific target sum. Store each prefix sum value in a hashmap as you traverse. For each new prefix sum, check whether (prefixSum - k) exists in the map — if it does, one or more subarrays ending at the current index sum to exactly k.

LeetCode 560 (Subarray Sum Equals K) is the classic application. Initialize the map with {0: 1} to handle subarrays starting from index 0. Traverse left to right: count += map.get(prefixSum - k, 0); map[prefixSum] += 1. LeetCode 523 (Continuous Subarray Sum) uses the same technique but stores prefix sum modulo k to find subarrays whose sum is a multiple of k.

This pattern runs in O(n) time and O(n) space. It handles negative numbers, unlike sliding window approaches. Whenever a problem asks "count subarrays with sum equal to k" or "find subarray whose sum is divisible by k", reach for prefix sum plus hashmap.

Prefix XOR applies the same precomputation idea but with the XOR operator instead of addition. Define prefixXOR[i] = arr[0] XOR arr[1] XOR ... XOR arr[i-1], with prefixXOR[0] = 0. The XOR of elements from index l to r is then prefixXOR[r+1] XOR prefixXOR[l] — identical in form to the range sum formula.

LeetCode 1310 (XOR Queries of a Subarray) is the canonical application — build prefixXOR in O(n) and answer each query in O(1). LeetCode 1442 (Count Triplets That Can Form Two Equal XOR Arrays) uses prefix XOR to find ranges where the XOR is 0, because if prefixXOR[i] == prefixXOR[j], the XOR of elements from i to j-1 is zero.

Prefix XOR is also used in trie-based maximum XOR problems (LeetCode 421), where prefix XOR values are inserted into a trie and queried greedily. Recognizing that "XOR over a range" decomposes the same way as "sum over a range" is the key insight.

A difference array inverts the prefix sum relationship: instead of querying cumulative sums, you perform batch range updates efficiently. To add value v to all elements from index l to r, apply diff[l] += v and diff[r+1] -= v. After all updates, take the prefix sum of diff to materialize the final array. Each update is O(1); materialization is O(n).

LeetCode 2381 (Shifting Letters II) gives multiple shift operations over character ranges and asks for the final string. With a difference array, each shift is a +1 or -1 update to a range — all recorded in O(1) per operation. LeetCode 1109 (Corporate Flight Bookings) asks for passenger counts per flight segment given range booking operations — difference array gives O(1) per booking and O(n) to produce the result.

Use difference arrays whenever the problem requires many range increment/decrement operations on an initially zero (or known) array, and only requires reading the final state. This is the reverse of the prefix sum use case: prefix sums accelerate reads; difference arrays accelerate writes.

The 2D prefix sum extends the 1D idea to matrices. Define prefix[i][j] as the sum of all elements in the rectangle from (0,0) to (i-1, j-1). Build using inclusion-exclusion: prefix[i][j] = matrix[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]. Initialize an (m+1) x (n+1) matrix of zeros to avoid boundary checks.

To query the sum of a rectangle from (r1, c1) to (r2, c2) (0-indexed): regionSum = prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]. LeetCode 304 (Range Sum Query 2D Immutable) is the direct application. LeetCode 1314 (Matrix Block Sum) uses 2D prefix sums to compute each cell's answer from a sliding rectangular window.

The build cost is O(m*n) and each query costs O(1). The +prefix[r1][c1] term in the query formula corrects for double-subtraction of the top-left sub-rectangle — this inclusion-exclusion identity is the only tricky part of 2D prefix sums. Once the formula is memorized, implementation is straightforward.

Easy problems to start with: LeetCode 303 (Range Sum Query Immutable) for core 1D prefix sum, LeetCode 724 (Find Pivot Index) for applying prefix sums to index search, and LeetCode 1480 (Running Sum of 1D Array) for the most basic prefix sum construction.

Medium problems that apply the patterns: LeetCode 560 (Subarray Sum Equals K) for prefix sum plus hashmap, LeetCode 238 (Product of Array Except Self) for prefix product variant, LeetCode 2270 (Number of Ways to Split Array) for prefix sum queries, and LeetCode 2559 (Count Vowel Strings in Ranges) for range query on preprocessed data.

Hard problems for mastery: LeetCode 2381 (Shifting Letters II) for difference arrays with character shifts, LeetCode 304 (Range Sum Query 2D Immutable) for 2D prefix sums, and LeetCode 308 (Range Sum Query 2D Mutable) for combining 2D prefix sums with Binary Indexed Trees. Solving these in order builds the full prefix sum intuition.