Skip to main content
Prefix Sum

1D Prefix Sum

prefix[i] = nums[0] + nums[1] + ... + nums[i]. To get sum of elements from index L to R: prefix[R] − prefix[L−1]. Build once in O(n), query any range in O(1).

O(n) build, O(1) query
·
O(n)

How It Works

A 1D prefix sum precomputes cumulative totals: prefix[i] holds the sum of all elements from the start through index i. Building it takes one O(n) pass, since each entry is just the previous entry plus the current element. Afterward, any range sum from L to R collapses to prefix[R] minus prefix[L−1] — a single subtraction.

The win comes from amortizing work across queries. Answering Q range-sum questions by re-adding elements costs O(n) each, or O(n·Q) total; with the prefix array it drops to O(n + Q). A common refinement is padding the array with a leading zero so prefix[R+1] − prefix[L] avoids the L = 0 edge case.

Step-by-Step Visualization

Build prefix sum array
1
0
2
1
3
2
4
3
5
4
prefix[1]
1/4

Code

Java
static int[] buildPrefix(int[] nums) {
  int[] prefix = new int[nums.length];
  prefix[0] = nums[0];
  for (int i = 1; i < nums.length; i++) {
    prefix[i] = prefix[i - 1] + nums[i];
  }
  return prefix;
}

static int rangeSum(int[] prefix, int l, int r) {
  return l == 0 ? prefix[r] : prefix[r] - prefix[l - 1];
}

// Example: nums = [1,2,3,4,5], prefix = [1,3,6,10,15]
// rangeSum(1,3) = prefix[3] - prefix[0] = 10 - 1 = 9

Tips & Gotchas

1prefix[i] = sum of elements from index 0 to i
2Range sum [l, r] = prefix[r] - prefix[l-1]
3Build the prefix array in one pass before answering queries

Practice Problems

  • 1Range Sum Query - Immutable
  • 2Find Pivot Index
  • 3Product of Array Except Self
  • 4Subarray Sums Divisible by K

About the Prefix Sum Pattern

Build an auxiliary array where each element stores the cumulative sum from the start. Then any range sum [i, j] is just prefix[j] − prefix[i−1] in O(1). Transforms repeated sum queries from O(n) to O(1) each.

Key insight

When you see 'subarray', 'contiguous', or 'in-place', think arrays. The key is reducing brute-force O(n²) to O(n) using sliding window, two pointers, or prefix sums.

Common Array Interview Problems

  • Two Sum
  • Best Time to Buy & Sell Stock
  • Maximum Subarray
  • Merge Intervals
  • Product of Array Except Self
  • Container With Most Water

Frequently Asked Questions

When is a prefix sum worth building instead of just summing on demand?

Build it whenever you face repeated range queries or need to compare many subarray sums, since the O(n) preprocessing pays for itself after the first couple of queries. For a single one-off range sum, a direct loop is simpler and just as fast.

What if the array is updated between queries?

A plain prefix array becomes stale on any point update, and rebuilding it costs O(n). When updates and queries interleave, switch to a Fenwick tree (binary indexed tree) or segment tree, which support both operations in O(log n).

Does the idea extend beyond addition?

Yes — any operation with an inverse works, such as XOR (its own inverse) or products when no zeros are present. Operations like min and max lack inverses, so range queries on them require sparse tables or segment trees instead.