Prefix sum is a technique used to perform range sum queries on an array efficiently. By doing a little extra work upfront, you can answer the question "What is the sum of items from index $i$ to $j$?" in constant time.

Imagine you're tracking your daily step count:

• Monday: 100
• Tuesday: 200
• Wednesday: 150

If someone asks "How many steps total did you take on Tuesday and Wednesday?", you have to add $200 + 150 = 350$. Prefix Sum Approach: You keep a running total.

• Mon: 100
• Tue: 300 (100 + 200)
• Wed: 450 (300 + 150)

Now, the sum of Tue to Wed is simply Steps[Wed] - Steps[Mon] $\rightarrow$ $450 - 100 = 350$. One subtraction!

---

The Mathematical Formula

Given an array $A$, the prefix sum array $P$ is defined as: $P[i] = A[0] + A[1] + ... + A[i]$

To find the sum of range $[L, R]$: $Sum(L, R) = P[R] - P[L-1]$ (Note: If $L=0$, the sum is simply $P[R]$)

Complexity

• Pre-computation: $O(n)$ time and space.
• Range Query: $O(1)$ time.

Without prefix sum, every query would take $O(n)$ time. If you have $Q$ queries, the prefix sum brings the total time from $O(Q \times n)$ down to $O(n + Q)$.

---

javascript Standard
/**
 * Range Sum Query using Prefix Sum
 */
class RangeSum {
  constructor(arr) {
    this.prefix = new Array(arr.length).fill(0);
    this.prefix[0] = arr[0];
    
    // 1. Pre-compute the prefix sum array
    for (let i = 1; i < arr.length; i++) {
      this.prefix[i] = this.prefix[i - 1] + arr[i];
    }
  }

  // 2. Query any range in O(1)
  query(L, R) {
    if (L === 0) return this.prefix[R];
    return this.prefix[R] - this.prefix[L - 1];
  }
}

// Example Usage
const rs = new RangeSum([1, 2, 3, 4, 5]);
console.log(rs.query(1, 3)); // 2 + 3 + 4 = 9

---

When to use?

Whenever you see "Range Sum" or "Subarray Sum" problems.

Common Variants

1. 2D Prefix Sum: Used for finding the sum of sub-matrices.
2. XOR Prefix: Same concept but using XOR operation instead of addition.
3. Subarray Sum Equals K: Combine prefix sum with a HashMap to find the count of subarrays that sum to a specific value $K$ in $O(n)$ time.