Algorithms from zero
Prefix sums
You have an array of numbers and a stream of questions: “What is the sum of elements from index 3 to 7?” then “What is the sum from index 1 to 4?” then “From 5 to 9?” Computing each sum by traversing the subarray costs O(n) per query. But what if you precompute the cumulative sum at every position? Then you can answer each query in O(1) by subtraction. You pay O(n) time once to build the prefix array, then you get O(1) per query forever. This is the prefix-sum pattern.
After this lesson you can recognize when a range-query problem benefits from prefix sums, build a prefix array in O(n) time, answer range-sum queries in O(1) by subtraction, understand the off-by-one care required (using a prefix array of length n+1), and see how the same idea generalizes to prefix counts and 2D grids.
Prefix sum is a precomputation technique where you build an array that stores the cumulative sum from the start of the array to each index.
The problem without prefix sums:
Given an array arr = [2, 5, 1, 3, 4], you receive many range-sum queries. For example:
- Sum from index 1 to 3? You traverse and compute arr[1] + arr[2] + arr[3] = 5 + 1 + 3 = 9.
- Sum from index 0 to 2? You traverse and compute arr[0] + arr[1] + arr[2] = 2 + 5 + 1 = 8.
Each query costs O(n) in the worst case. With q queries, the total is O(n × q). That scales poorly.
The idea: precompute cumulative sums
Build a prefix array prefix of length n+1 (not n, but n+1!) where:
prefix[0] = 0(sum of zero elements)prefix[1] = arr[0](sum of first 1 element)prefix[2] = arr[0] + arr[1](sum of first 2 elements)prefix[k] = arr[0] + arr[1] + ... + arr[k-1](sum of first k elements)
For arr = [2, 5, 1, 3, 4], the prefix array is:
prefix = [0, 2, 7, 8, 11, 15]Now, to find the sum of elements from index i to j (inclusive), use this formula:
sum(i, j) = prefix[j+1] - prefix[i]Why? Because:
prefix[j+1]= sum of first j+1 elements = arr[0] + … + arr[j]prefix[i]= sum of first i elements = arr[0] + … + arr[i-1]- Subtract: arr[i] + arr[i+1] + … + arr[j]
Example:
- Sum from index 1 to 3:
prefix[4] - prefix[1] = 11 - 2 = 9✓ - Sum from index 0 to 2:
prefix[3] - prefix[0] = 8 - 0 = 8✓
The off-by-one care:
The key is using a prefix array of length n+1 (not n). This way, prefix[i] always represents the sum of the first i elements, and the formula sum(i, j) = prefix[j+1] - prefix[i] works cleanly at all edges without special cases.
Time and space tradeoff:
- Setup: O(n) time to build the prefix array.
- Space: O(n) extra memory for the prefix array.
- Per query: O(1) time.
- Total for q queries: O(n + q) instead of O(n × q).
This is the classic precomputation pattern: spend time and memory upfront once, then reuse the result many times at no cost. You saw a similar idea with two-pointer and sliding window (moving incrementally to avoid recomputation). Here you precompute to turn repeated work into instant lookups.
Let us code the prefix-sum pattern.
1. Build the prefix array:
function buildPrefix(arr) {
const n = arr.length;
const prefix = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + arr[i];
}
return prefix;
}2. Answer range-sum queries:
function rangeSum(prefix, i, j) {
// Sum of elements from index i to j (inclusive)
return prefix[j + 1] - prefix[i];
}Full example:
const arr = [2, 5, 1, 3, 4];
const prefix = buildPrefix(arr);
console.log(prefix); // [0, 2, 7, 8, 11, 15]
console.log(rangeSum(prefix, 1, 3)); // 5 + 1 + 3 = 9
console.log(rangeSum(prefix, 0, 2)); // 2 + 5 + 1 = 8
console.log(rangeSum(prefix, 0, 4)); // 2 + 5 + 1 + 3 + 4 = 15
console.log(rangeSum(prefix, 2, 4)); // 1 + 3 + 4 = 8Try running this:
Let us trace building the prefix array for [2, 5, 1, 3, 4]:
1
function buildPrefix(arr) {
2
const prefix = new Array(arr.length + 1).fill(0);
3
for (let i = 0; i < arr.length; i++) {
4
prefix[i + 1] = prefix[i] + arr[i];
5
}
6
return prefix;
7
}
Now trace a range-sum query. Find sum from index 1 to 3:
1
function rangeSum(prefix, i, j) {
2
return prefix[j + 1] - prefix[i];
3
}
| Operation | Time | Space | Notes |
|---|---|---|---|
| Build prefix array | O(n) | O(n) | Single pass, accumulate sum |
| Range-sum query | O(1) | O(1) | Two lookups and one subtraction |
| q queries total | O(n + q) | O(n) | Setup once, query many times |
Comparison to naive approach:
| Approach | Build Time | Per Query | Total for q Queries |
|---|---|---|---|
| Naive (traverse each query) | O(1) | O(n) | O(n × q) |
| Prefix sum | O(n) | O(1) | O(n + q) |
If q is large (many queries), prefix sums win by a huge margin. If q = 1000 and n = 100, naive is 100,000 operations; prefix sum is 1,100 operations. Nearly 100× faster.
When is it worth it?
Use prefix sums if:
- You have many range-sum queries on the same array.
- The array does not change (static).
Do not use if:
- You have only one or two queries.
- The array changes frequently (you must rebuild prefix on each change, costing O(n)).
Build the prefix array for [3, 1, 4, 1, 5]. What is prefix[3]?
Using prefix array [0, 3, 4, 8, 9, 14] (from the array [3, 1, 4, 1, 5]), what is the sum from index 1 to 3?
Why do we create a prefix array of length n+1 instead of n?
An array has 10,000 elements. You will answer 5,000 range-sum queries. Approximately how much faster is the prefix-sum approach than the naive traversal per query?
If the original array changes (e.g., you update arr[3]), what happens to the prefix array?
Common mistake
Off-by-one indexing. The most common mistake: confusing which prefix array index to use. Remember: prefix[k] = sum of the first k elements (indices 0 to k-1). To query the sum from index i to j, subtract prefix[j+1] - prefix[i]. If you use prefix[j] - prefix[i-1], you will get the wrong result. Always draw it out with a small example first.
Edge cases
Query from index 0. If you want the sum from index 0 to j (the start of the array), the formula is prefix[j+1] - prefix[0]. Since prefix[0] = 0, this simplifies to prefix[j+1], which is correct. The zero at the start handles this edge case automatically.
Why is the prefix-sum technique a good example of the time–space tradeoff you learned about in Big-O?
The prefix-sum technique precomputes cumulative sums to answer range-sum queries in O(1).
Key facts:
-
The prefix array:
prefix[k]= sum of the first k elements (arr[0] to arr[k-1]). Initializeprefix[0] = 0. Build in O(n) time. -
Range-sum formula: sum of elements from index i to j =
prefix[j+1] - prefix[i]. This works because of the zero at the start. -
Why it works: Subtracting two cumulative sums cancels out the part before index i, leaving only the part from i to j.
-
Time–space tradeoff: Spend O(n) time and O(n) space to build. Then each query is O(1). Total for q queries: O(n + q) instead of O(n × q).
-
When to use: Many queries on a static array. If the array changes, you must rebuild.
-
Generalization: The same idea extends to prefix counts (how many elements in a range satisfy a condition?), 2D prefix sums (rectangular region sums), and more. The pattern is always the same: precompute once, reuse forever.
Next, you will explore hashing (storing and retrieving values by key in O(1)) and then data structures like stacks and queues.