Prefix Sum

Prefix sum is a “pay once, query many” strategy. You precompute cumulative information so that each later range query becomes constant time.

This is one of the most reusable ideas in DSA and systems work (analytics, dashboards, telemetry windows, histogram accumulation).

Core Definition

For array arr, define:

prefix[i] = arr[0] + arr[1] + ... + arr[i - 1]

So prefix has length n + 1 and starts with 0.

function buildPrefix(arr: number[]): number[] {
  const prefix = new Array(arr.length + 1).fill(0)
  for (let i = 0; i < arr.length; i++) {
    prefix[i + 1] = prefix[i] + arr[i]
  }
  return prefix
}

Range query [l..r] (inclusive, 0-indexed):

function rangeSum(prefix: number[], l: number, r: number): number {
  return prefix[r + 1] - prefix[l]
}

Why subtraction works

• prefix[r + 1] includes sum up to r
• prefix[l] includes sum before l
• subtract to isolate l..r

When Prefix Sum Is the Right Tool

Use it when:

1. data is static or mostly static
2. many range queries are required
3. aggregate operation is invertible via subtraction-like cancellation

Not ideal when:

• frequent point/range updates are mixed with queries -> Fenwick/Segment Tree
• one query only -> direct loop may be simpler

Pattern 1: Prefix + Frequency Map (Subarray Count Problems)

This is the high-value interview pattern.

Problem: count subarrays with sum exactly k

function subarraySum(nums: number[], k: number): number {
  const freq = new Map<number, number>()
  freq.set(0, 1) // empty prefix

  let prefix = 0
  let ans = 0

  for (const x of nums) {
    prefix += x
    ans += freq.get(prefix - k) ?? 0
    freq.set(prefix, (freq.get(prefix) ?? 0) + 1)
  }
  return ans
}

Invariant

At each index r, map stores frequencies of all prefix sums ending before r.

Number of valid starts l for this r is count of prior prefix sums equal to currentPrefix - k.

Critical ordering bug to avoid

Always query map first, then insert current prefix. If you insert first, you’ll overcount zero-length windows.

Pattern 2: Prefix Modulo Classes

Many “divisible by K” problems are prefix modulo problems.

Problem: subarray sums divisible by k

If:

(prefix[r] - prefix[l]) % k == 0

then:

prefix[r] % k == prefix[l] % k

So count equal remainders.

function subarraysDivByK(nums: number[], k: number): number {
  const freq = new Map<number, number>()
  freq.set(0, 1)

  let prefix = 0
  let ans = 0

  for (const x of nums) {
    prefix += x
    let mod = prefix % k
    if (mod < 0) mod += k // handle negative sums

    ans += freq.get(mod) ?? 0
    freq.set(mod, (freq.get(mod) ?? 0) + 1)
  }
  return ans
}

Negative modulo normalization (if (mod < 0) mod += k) is a common miss.

Pattern 3: Equal 0/1 Counts via Prefix Transform

Convert:

• 0 -> -1
• 1 -> +1

Now equal zeros and ones means transformed sum is 0.

Longest subarray with equal 0 and 1

function findMaxLength(nums: number[]): number {
  const firstSeen = new Map<number, number>()
  firstSeen.set(0, -1) // prefix sum 0 before start

  let prefix = 0
  let best = 0

  for (let i = 0; i < nums.length; i++) {
    prefix += nums[i] === 1 ? 1 : -1

    if (firstSeen.has(prefix)) {
      best = Math.max(best, i - firstSeen.get(prefix)!)
    } else {
      firstSeen.set(prefix, i)
    }
  }
  return best
}

For longest-range variants, store first occurrence only.

Pattern 4: Prefix Product / Bidirectional Prefix (Product Except Self)

Not additive prefix sum, but same “accumulate from one side, combine with opposite side” idea.

function productExceptSelf(nums: number[]): number[] {
  const n = nums.length
  const out = new Array(n).fill(1)

  let pref = 1
  for (let i = 0; i < n; i++) {
    out[i] = pref
    pref *= nums[i]
  }

  let suff = 1
  for (let i = n - 1; i >= 0; i--) {
    out[i] *= suff
    suff *= nums[i]
  }
  return out
}

Useful mental extension: prefix logic is broader than sums.

Pattern 5: Difference Array (Range Updates)

Prefix sum answers range queries fast.
Difference array performs range updates fast.

For updates “add val to all arr[l..r]”:

• diff[l] += val
• diff[r + 1] -= val (if in bounds)

Then one prefix pass reconstructs final array.

function applyRangeAdds(n: number, updates: Array<[number, number, number]>): number[] {
  const diff = new Array(n + 1).fill(0)

  for (const [l, r, val] of updates) {
    diff[l] += val
    if (r + 1 < n) diff[r + 1] -= val
  }

  const arr = new Array(n).fill(0)
  let run = 0
  for (let i = 0; i < n; i++) {
    run += diff[i]
    arr[i] = run
  }
  return arr
}

This pattern appears in batch scheduling, timeline increments, and interval load aggregation.

2D Prefix Sum (Matrix Queries)

Define:

p[r][c] = sum of rectangle (0,0) to (r-1,c-1)

function build2D(matrix: number[][]): number[][] {
  const rows = matrix.length
  const cols = matrix[0].length
  const p = Array.from({ length: rows + 1 }, () => new Array(cols + 1).fill(0))

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      p[r + 1][c + 1] =
        matrix[r][c] +
        p[r][c + 1] +
        p[r + 1][c] -
        p[r][c]
    }
  }
  return p
}

function query2D(p: number[][], r1: number, c1: number, r2: number, c2: number): number {
  return p[r2 + 1][c2 + 1] - p[r1][c2 + 1] - p[r2 + 1][c1] + p[r1][c1]
}

Inclusion-exclusion intuition

• add big rectangle to bottom-right
• subtract top strip and left strip
• overlapping top-left got subtracted twice, so add back once

Common Pitfalls Checklist

1. Off-by-one (prefix length must be n + 1)
2. Forgetting freq.set(0, 1) bootstrap
3. Updating map before querying for counts
4. Ignoring negative modulo normalization
5. Integer overflow in non-JS languages (long long / long)
6. Using prefix when online updates are required
7. Confusing inclusive vs exclusive boundaries

Prefix Sum vs Sliding Window

If negatives exist and condition is exact/count-style, prefix often beats sliding window.

Interview Communication Script

Say this clearly:

1. “Let prefix[i] be sum of first i numbers.”
2. “Subarray l..r equals prefix[r+1] - prefix[l].”
3. “I track prior prefix frequencies to count valid starts in O(1) each.”
4. “One pass, so O(n) time, O(n) space.”

This turns your solution from memorized code into reasoning.

Problem Ladder

Easy

• Range Sum Query (immutable)
• Running Sum of 1D Array

Medium

• Subarray Sum Equals K
• Continuous Subarray Sum
• Subarrays Divisible by K
• Product of Array Except Self

Hard / high-signal

• Maximum Size Subarray Sum Equals K
• Count of Range Sum
• Number of Submatrices That Sum to Target

Complexity Summary

Final Takeaway

Prefix sum is about algebraic reframing:

• turn range properties into differences of cumulative states
• then count or query those states efficiently

Once you internalize this transform, many “hard-looking” subarray problems collapse into simple map accounting in one pass.