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.

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.

Diagram

Pattern control flow (customize nodes for this pattern). camelCase node IDs.

Loading diagram…

Mental Model

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

1D static ranges: build prefix with prefix[index] = prefix[index-1] + values[index]; answer prefix[right] - prefix[left-1].
2D static submatrix: build explicit sum[row][col] as cumulative rectangle from origin; query with inclusion–exclusion on four corners.
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.
Subarray sum equals target: iterate values, track running currentPrefix; add to answer count[currentPrefix - target]; then increment count[currentPrefix].
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.

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

238. Product of Array Except Self — prefix and suffix products (same cumulative idea)
209. Minimum Size Subarray Sum — sliding window on positive array (prefix-window dual view)
437. Path Sum III — prefix accumulation on root-to-node paths

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.

On this page