Precompute cumulative sums to answer range queries in O(1) after O(n) preprocessing.
A prefix sum array stores cumulative totals so that the sum of any subarray [i, j] can be computed in O(1) as prefix[j+1] - prefix[i]. This pattern is essential for range sum queries, subarray sum problems, and 2D matrix range queries.
Build O(n) · Query O(1)
O(n) for prefix array
Learn the core patterns in this topic. Each block explains when to use the pattern, the intuition behind it, and a compact code example.
Use this when many range-sum queries are asked on the same array
Instead of recomputing each subarray sum from scratch, precompute cumulative totals once. This changes repeated range queries from O(n) each to O(1) each after preprocessing.
Problem Range Sum Query. Build a prefix array where prefix[i + 1] stores the sum of the first i + 1 elements.
// Build prefix array — Range Sum Query
function buildPrefix(nums) {
const prefix = [0];
for (const num of nums) prefix.push(prefix[prefix.length - 1] + num);
return prefix;
}
// rangeSum(prefix, 1, 3) gives sum of nums[1..3]
function rangeSum(prefix, left, right) {
return prefix[right + 1] - prefix[left];
}Use this because the sum from index left to right can be isolated by removing everything before left from the prefix ending at right
This is the core mathematical identity behind prefix sums. Once understood, many array and matrix problems become much easier.
Problem Sum of Subarray [i, j]. Answer it in O(1) using prefix[j + 1] - prefix[i].
// Range sum by subtraction — O(1) query
// prefix[j+1] - prefix[i] gives sum of nums[i..j]
function rangeQuery(nums, queries) {
const prefix = [0];
for (const num of nums) prefix.push(prefix[prefix.length - 1] + num);
return queries.map(([l, r]) => prefix[r + 1] - prefix[l]);
}Use this when you do not need to answer arbitrary old queries later, but you still need prefix reasoning while scanning
In that case, a single running sum variable is enough. This appears in many counting and optimization problems.
Problem Maximum Prefix Value Seen So Far. Update the running sum as you iterate and use it immediately instead of storing every prefix.
// Running total without storing full array
// Product of Array Except Self — prefix & suffix running products
function productExceptSelf(nums) {
const n = nums.length, result = new Array(n).fill(1);
let prefix = 1;
for (let i = 0; i < n; i++) { result[i] = prefix; prefix *= nums[i]; }
let suffix = 1;
for (let i = n - 1; i >= 0; i--) { result[i] *= suffix; suffix *= nums[i]; }
return result;
}Use this when the question asks how many subarrays satisfy a condition involving sums
Instead of checking all start positions, record how often each previous prefix sum has appeared. The current prefix can then instantly determine how many earlier starts create a valid subarray.
Problem Subarray Sum Equals K. If currentSum - k has appeared before, then every such occurrence defines a valid subarray ending here.
// Prefix sum + hash map — Subarray Sum Equals K
function subarraySum(nums, k) {
const freq = new Map([[0, 1]]);
let sum = 0, count = 0;
for (const num of nums) {
sum += num;
count += freq.get(sum - k) ?? 0;
freq.set(sum, (freq.get(sum) ?? 0) + 1);
}
return count;
}Use this when the input is a matrix and you need rectangular region sums
The same prefix idea works in two dimensions, but you must subtract the overlapped area once. This is a direct extension of 1D prefix thinking.
Problem Range Sum Query 2D. Build prefix[row][col] using top, left, and top-left values so any rectangle can be answered in O(1).
// 2D prefix sum — Range Sum Query 2D Immutable
function buildPrefix2D(grid) {
const rows = grid.length, cols = grid[0].length;
const prefix = Array.from({length: rows+1}, () => new Array(cols+1).fill(0));
for (let r = 1; r <= rows; r++)
for (let c = 1; c <= cols; c++)
prefix[r][c] = grid[r-1][c-1] + prefix[r-1][c] + prefix[r][c-1] - prefix[r-1][c-1];
return prefix;
}
function sumRegion(prefix, r1, c1, r2, c2) {
return prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1];
}Use this when the problem gives many interval additions and asks for the final array
Instead of updating every index in every range, record only where each update starts and stops, then reconstruct the array with one final prefix pass. This turns repeated O(length of range) work into O(1) per update.
Problem Range Addition. For an update [l, r] += val, do diff[l] += val and diff[r + 1] -= val when valid, then prefix-sum the diff array.
// Difference array — Range Addition updates in O(1) each
function applyUpdates(length, updates) {
const diff = new Array(length).fill(0);
for (const [l, r, val] of updates) {
diff[l] += val;
if (r + 1 < length) diff[r + 1] -= val;
}
for (let i = 1; i < length; i++) diff[i] += diff[i - 1];
return diff;
}