All Roadmaps›🧠 Data Structures & Algorithms›Phase 3›Prefix Sum & Range Queries

Prefix Sum & Range Queries

0/12 in this phase0/57 across the roadmap

📖 Concept

Prefix sum (cumulative sum) pre-computes running totals so that any range sum can be answered in O(1) time after O(n) preprocessing.

Core idea:

Array:      [3, 1, 4, 1, 5, 9]
Prefix sum: [3, 4, 8, 9, 14, 23]
Sum(i..j):  prefix[j] - prefix[i-1]
Sum(2..4):  14 - 4 = 10  ←  (4 + 1 + 5)

Why it matters: Without prefix sum, each range query is O(n). With it, O(1) per query. If you have Q queries on an array of size n: O(nQ) → O(n + Q).

Variations:

  1. 1D prefix sum — range sum in arrays
  2. 2D prefix sum — submatrix sum in grids
  3. Prefix XOR — range XOR queries
  4. Difference array — range update in O(1), final values in O(n)

Combined with hash map: Prefix sum + hash map solves "count subarrays with sum = k" in O(n). This is a TOP interview pattern.

🏠 Real-world analogy: A running odometer in a car. To find distance traveled between mile 50 and mile 120, you don't re-drive — you subtract: 120 - 50 = 70 miles. That's prefix sum.

💻 Code Example

codeTap to expand ⛶
1// BUILD PREFIX SUM
2function buildPrefix(arr: number[]): number[] {
3  const prefix: number[] = [arr[0]];
4  for (let i = 1; i < arr.length; i++) {
5    prefix[i] = prefix[i - 1] + arr[i];
6  }
7  return prefix;
8}
9

10// RANGE SUM QUERY — O(1) per query
11function rangeSum(prefix: number[], i: number, j: number): number {
12  return i === 0 ? prefix[j] : prefix[j] - prefix[i - 1];
13}
14

15// SUBARRAY SUM EQUALS K — Prefix sum + hash map
16function subarraySum(nums: number[], k: number): number {
17  const prefixCount = new Map<number, number>([[0, 1]]);
18  let sum = 0, count = 0;
19  for (const num of nums) {
20    sum += num;
21    if (prefixCount.has(sum - k)) {
22      count += prefixCount.get(sum - k)!;
23    }
24    prefixCount.set(sum, (prefixCount.get(sum) || 0) + 1);
25  }
26  return count;
27}
28// Key insight: if prefix[j] - prefix[i] = k, subarray (i,j] sums to k
29

30// 2D PREFIX SUM — Submatrix sum in O(1)
31function build2DPrefix(matrix: number[][]): number[][] {
32  const m = matrix.length, n = matrix[0].length;
33  const p: number[][] = Array.from({ length: m }, () => new Array(n).fill(0));
34  for (let i = 0; i < m; i++) {
35    for (let j = 0; j < n; j++) {
36      p[i][j] = matrix[i][j]
37        + (i > 0 ? p[i-1][j] : 0)
38        + (j > 0 ? p[i][j-1] : 0)
39        - (i > 0 && j > 0 ? p[i-1][j-1] : 0);
40    }
41  }
42  return p;
43}
44

45// PRODUCT EXCEPT SELF — Prefix and suffix products
46function productExceptSelf(nums: number[]): number[] {
47  const n = nums.length;
48  const result = new Array(n).fill(1);
49  let prefix = 1;
50  for (let i = 0; i < n; i++) {
51    result[i] = prefix;
52    prefix *= nums[i];
53  }
54  let suffix = 1;
55  for (let i = n - 1; i >= 0; i--) {
56    result[i] *= suffix;
57    suffix *= nums[i];
58  }
59  return result;
60}
61

62// DIFFERENCE ARRAY — Range updates in O(1)
63function rangeAdd(diff: number[], l: number, r: number, val: number): void {
64  diff[l] += val;
65  if (r + 1 < diff.length) diff[r + 1] -= val;
66}
67function buildFromDiff(diff: number[]): number[] {
68  const result = [diff[0]];
69  for (let i = 1; i < diff.length; i++) {
70    result[i] = result[i - 1] + diff[i];
71  }
72  return result;
73}

🏋️ Practice Exercise

Practice Problems (Easy → Hard):

  1. Build a prefix sum array and answer range sum queries
  2. Running sum of a 1D array
  3. Find pivot index (left sum equals right sum)
  4. Count subarrays with sum equal to k (prefix sum + hash map)
  5. Product of array except self (without division)
  6. Maximum subarray sum using prefix sum
  7. Check if subarray with sum 0 exists
  8. Range XOR queries using prefix XOR
  9. 2D prefix sum — submatrix sum queries
  10. Difference array — apply multiple range updates efficiently

⚠️ Common Mistakes

  • Off-by-one when computing range sum — rangeSum(i, j) = prefix[j] - prefix[i-1], handle i=0 separately

  • Not considering negative numbers — prefix sum works with negatives, but some optimizations (like pruning) don't

  • Forgetting the base case {0: 1} in the hash map for subarray sum = k — counts subarrays starting from index 0

  • Using prefix sum for single queries — not worth it for one-time range sum (just loop)

  • Not recognizing prefix sum pattern — keywords: 'range', 'subarray sum', 'cumulative'

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Prefix Sum & Range Queries

← PreviousSliding Window PatternNext →Binary Search — Advanced Applications