THN Interview Prep

16. Prefix Sum / Difference Array

TL;DR

Store cumulative sums (or 2D cumulative areas) so any range sum becomes two boundary lookups in (O(1)) after (O(n)) or (O(m n)) preprocessing. For many range-add-one-value updates on an array, use a difference array and convert back with a prefix pass. When you need how often a subarray sums to a target, track frequencies of prefix sums in a hash map: currentPrefix - target means a prior prefix completed the segment.

Core Basics

  • Object: cumulative array for range sums in (O(1)) after (O(n)) build; difference array for range adds.
  • 2D / frequency: same idea on matrices or hash of prefix counts.
  • Staff-level bar: connect to offline queries and coordinate compression when indices are huge.

Recognition Cues

  • Phrases: "sum of elements from index left to right", "submatrix sum", "range update then final values", "subarray with sum equals k", "contiguous segment sum", "2D range query".
  • Shapes: static array with many range-sum queries; matrix with rectangle queries; offline range additions; stream of prefix sums paired with a target.
  • Clues for difference array: "add value to every index in [left, right]" many times, then output final array.

Use-case Lens

  • Best when: many range sums/counts/updates can be answered by reusing cumulative state instead of rescanning.
  • Not for: range min/max with updates; use segment tree/Fenwick/monotonic structures.
  • Main invariant: prefix[i] stores everything before i, so range [l, r] is a subtraction of two snapshots.
  • Interview move: for subarray sum equals k, explain why you count previous prefixes equal to current - k.

Diagram

Loading diagram…

Step-by-step Visual

Example: Count subarrays with sum 3 in [1, 2, 3]. Store how many times each prefix sum has appeared.

Loading diagram…

Understanding

A prefix sum prefix[index] is the sum of all elements before exclusiveEnd = index + 1. Then rangeSum(left, right) = prefix[right] - prefix[left-1] (with prefix[-1] treated as 0). In 2D, think of a table of rectangle sums from (0,0); inclusion–exclusion subtracts top and left strips and adds back the double-counted corner. A difference array stores increments at boundaries: adding value on [left, right] is diff[left] += value, diff[right+1] -= value; prefixing diff reconstructs actual values. For sum equals k, the equation prefix[right] - prefix[left-1] == target rearranges to prefix[left-1] == prefix[right] - target, so counting pairs reduces to counting how many earlier prefixes equal currentPrefix - target.

Generic Recipe

  1. 1D static ranges: build prefix with prefix[index] = prefix[index-1] + values[index]; answer prefix[right] - prefix[left-1].
  2. 2D static submatrix: build explicit sum[row][col] as cumulative rectangle from origin; query with inclusion–exclusion on four corners.
  3. Range updates, point queries: maintain diff; for each update [left, right], adjust diff[left] and diff[right+1]; finish with one prefix sum over diff.
  4. Subarray sum equals target: iterate values, track running currentPrefix; add to answer count[currentPrefix - target]; then increment count[currentPrefix].
  5. Watch off-by-one: define prefix as exclusive-end or inclusive consistently; 2D indices often use extra row/column of zeros.

Complexity

  • Time: building 1D prefix (O(n)), each range query (O(1)); 2D build (O(m n)), query (O(1)); difference array each update (O(1)), final prefix (O(n)); hashmap subarray count (O(n)) one pass.
  • Space: (O(n)) or (O(m n)) for tables; hash map (O(n)) distinct prefixes in worst case.

Memory Hooks

  • Operational mantra: store cumulative state so every range becomes current prefix minus an earlier prefix.
  • Anti-panic: convert range work to "prefix at right minus prefix before left"; then choose array, map, or difference array.

Study Pattern (SDE3+)

  • Recognition drill (10 min): spot range sum, subarray sum equals K, path-sum prefix, and range-update prompts.
  • Implementation sprint (25 min): code subarray sum with a frequency map and one difference-array range update.
  • Staff follow-up (10 min): discuss negative numbers, streaming prefixes, overflow, and 2D prefix sums.

Generic Code Template

Go

package main

// One-dimensional prefix sums; query inclusive range [left, right].
func buildPrefixSum(values []int) []int {
	length := len(values)
	prefix := make([]int, length+1)
	for index := 0; index < length; index++ {
		prefix[index+1] = prefix[index] + values[index]
	}
	return prefix
}

func rangeSum(prefix []int, left, right int) int {
	return prefix[right+1] - prefix[left]
}

// Subarray count with sum exactly equal to target (prefix frequency map).
func countSubarraysSumTarget(values []int, target int) int {
	countByPrefix := map[int]int{0: 1}
	currentPrefix := 0
	answer := 0
	for _, value := range values {
		currentPrefix += value
		need := currentPrefix - target
		answer += countByPrefix[need]
		countByPrefix[currentPrefix]++
	}
	return answer
}

type rangeAdd struct {
	left, right, value int
}

func materializeAfterRangeAdds(length int, updates []rangeAdd) []int {
	diff := make([]int, length+1)
	for _, update := range updates {
		diff[update.left] += update.value
		if update.right+1 < len(diff) {
			diff[update.right+1] -= update.value
		}
	}
	out := make([]int, length)
	current := 0
	for index := 0; index < length; index++ {
		current += diff[index]
		out[index] = current
	}
	return out
}

// Two-dimensional prefix (padding row 0 / col 0 are zeros).
func build2DPrefixSum(grid [][]int) [][]int {
	rows := len(grid)
	cols := len(grid[0])
	sum := make([][]int, rows+1)
	for row := range sum {
		sum[row] = make([]int, cols+1)
	}
	for row := 1; row <= rows; row++ {
		for col := 1; col <= cols; col++ {
			sum[row][col] = grid[row-1][col-1] + sum[row-1][col] + sum[row][col-1] - sum[row-1][col-1]
		}
	}
	return sum
}

func submatrixSum(sum [][]int, top, left, bottom, right int) int {
	return sum[bottom+1][right+1] - sum[top][right+1] - sum[bottom+1][left] + sum[top][left]
}

func main() {}

JavaScript

function buildPrefixSum(values) {
  const prefix = new Array(values.length + 1).fill(0);
  for (let index = 0; index < values.length; index += 1) {
    prefix[index + 1] = prefix[index] + values[index];
  }
  return prefix;
}

function rangeSum(prefix, left, right) {
  return prefix[right + 1] - prefix[left];
}

function countSubarraysSumTarget(values, target) {
  const countByPrefix = new Map([[0, 1]]);
  let currentPrefix = 0;
  let answer = 0;
  for (const value of values) {
    currentPrefix += value;
    const need = currentPrefix - target;
    answer += countByPrefix.get(need) ?? 0;
    countByPrefix.set(currentPrefix, (countByPrefix.get(currentPrefix) ?? 0) + 1);
  }
  return answer;
}

function materializeAfterRangeAdds(length, ranges) {
  const diff = new Array(length + 1).fill(0);
  for (const { left, right, value } of ranges) {
    diff[left] += value;
    if (right + 1 < diff.length) {
      diff[right + 1] -= value;
    }
  }
  const result = [];
  let current = 0;
  for (let index = 0; index < length; index += 1) {
    current += diff[index];
    result.push(current);
  }
  return result;
}

function build2DPrefixSum(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  const sum = Array.from({ length: rows + 1 }, () => new Array(cols + 1).fill(0));
  for (let row = 1; row <= rows; row += 1) {
    for (let col = 1; col <= cols; col += 1) {
      sum[row][col] =
        grid[row - 1][col - 1] +
        sum[row - 1][col] +
        sum[row][col - 1] -
        sum[row - 1][col - 1];
    }
  }
  return sum;
}

function submatrixSum(sum, top, left, bottom, right) {
  return (
    sum[bottom + 1][right + 1] -
    sum[top][right + 1] -
    sum[bottom + 1][left] +
    sum[top][left]
  );
}

Variants

  • 1D prefix / rolling: single array of queries; sometimes compress to one variable runningSum if you only need streaming counts (see hash map variant).
  • 2D prefix: sum[row][col] stores rectangle sum from (0,0) to (row-1,col-1) in 1-based padding layout; query uses four terms.
  • Difference array + prefix: many interval adds, one final state (car pooling, corporate flight bookings style).
  • Prefix on tree paths: same frequency idea on root-to-node cumulative weight (path problems).

Representative Problems

Anti-patterns

  • Using a raw loop over each query (O(n \cdot q)) when static prefix would yield (O(n + q)).
  • Mixing inclusive/exclusive prefix definitions mid-solution (especially in 2D padding).
  • Applying difference array without a final prefix pass to recover actual values.
  • For subarray sum k, resetting the map incorrectly—always seed 0 with count 1 for empty prefix before the first element.

Mark this page when you finish learning it.

Last updated on

Spotted something unclear or wrong on this page?

On this page

16. Prefix Sum / Difference ArrayTL;DRCore BasicsRecognition CuesUse-case LensDiagramStep-by-step VisualUnderstandingGeneric RecipeComplexityMemory HooksStudy Pattern (SDE3+)Generic Code TemplateGoJavaScriptVariantsRepresentative ProblemsAnti-patterns