➕ Prefix Sum

One-line summary: Pre-compute cumulative sums so any range query sum(L..R) is answered in O(1) after O(n) preprocessing.

---

Concept

Build a prefix sum array p where p[i] = arr[0] + arr[1] + ... + arr[i].

Range sum [L, R] = p[R] - p[L-1]   (with p[-1] = 0)

Difference array is the inverse: apply range updates in O(1), read values in O(n).

---

Diagram

---

Time & Space Complexity

Operation	Time	Space
Build prefix array	O(n)	O(n)
Range query	O(1)	O(1)
Difference array update	O(1)	O(n)

---

Common Patterns

Basic Prefix Sum

function buildPrefix(arr) {
  const p = new Array(arr.length + 1).fill(0);
  for (let i = 0; i < arr.length; i++) p[i + 1] = p[i] + arr[i];
  return p;
}
function rangeSum(p, l, r) { return p[r + 1] - p[l]; }

Subarray Sum Equals K (hash map + prefix)

function subarraySum(nums, k) {
  const map = new Map([[0, 1]]);
  let count = 0, sum = 0;
  for (const n of nums) {
    sum += n;
    count += (map.get(sum - k) || 0);
    map.set(sum, (map.get(sum) || 0) + 1);
  }
  return count;
}

---

Pitfalls

• Off-by-one: use 1-indexed prefix array to avoid p[-1] issues
• 2D prefix sum: remember the inclusion-exclusion formula

---

Practice Problems

Problem	Difficulty	Solution
LC 1480 — Running Sum of 1D Array	Easy
LC 303 — Range Sum Query	Easy
LC 560 — Subarray Sum Equals K	Medium
LC 525 — Contiguous Array	Medium
LC 304 — Range Sum Query 2D	Medium
LC 1171 — Remove Zero Sum Consecutive Nodes	Medium
CC — Sumtastic (SUMTASTIC)	Medium
CC — Chef Segment (CHSEG)	Medium
LC 363 — Max Sum of Rectangle No Larger Than K	Hard
LC 930 — Binary Subarrays With Sum	Medium
LC 523 — Continuous Subarray Sum	Medium
LC 238 — Product of Array Except Self	Medium
LC 724 — Find Pivot Index	Easy
LC 1031 — Maximum Sum of Two Non-Overlapping Subarrays	Medium
LC 1094 — Car Pooling	Medium
LC 1109 — Corporate Flight Bookings	Medium
LC 1248 — Count Number of Nice Subarrays	Medium
LC 1314 — Matrix Block Sum	Medium
LC 1442 — Count Triplets That Can Form Two Arrays of Equal XOR	Medium
LC 1590 — Make Sum Divisible by P	Medium
LC 1658 — Minimum Operations to Reduce X to Zero	Medium
LC 1664 — Ways to Make a Fair Array	Medium
LC 1732 — Find the Highest Altitude	Easy
LC 1991 — Find the Middle Index in Array	Easy
CC — Range Sum Queries (RANGESUM)	Easy
CC — Prefix Sum Array (PREFSUM)	Easy
CC — Subarray Queries (SUBARR)	Medium

---

Related Topics

• Hashing — hash map powers subarray sum = K
• Kadane's Algorithm — complementary
• Sliding Window

← Back to Home · © sparshjaswal