Skip to main content

Prefix Sums (Cumulative Sums)

Overview​

A prefix sum is a powerful precomputation technique where we store the cumulative totals of values in a structure, enabling fast range queries and reducing repeated computation.

At its simplest: For an array arr[0..n-1], the prefix sum array ps is defined as:

ps[0] = arr[0]
ps[i] = ps[i-1] + arr[i], for i ≥ 1

This transforms queries like “sum of elements between l and r” from O(n) to O(1).

1. Prefix Sums on Arrays​

Construction: O(n) Range Query: O(1) Space: O(n)

Formula:

sum(l..r) = ps[r] - ps[l-1]   (with ps[-1] = 0 by convention)

Example:

arr = [2, 4, 5, 3]
ps  = [2, 6, 11, 14]

sum(1..3) = ps[3] - ps[0] = 12

2. Prefix Sums on Matrices (2D Prefix Sums)​

For a matrix M, construct P where each cell (i,j) stores the sum of the submatrix (0,0) to (i,j).

Formula:

P[i][j] = M[i][j] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]

This allows submatrix sum queries in O(1):

sum((x1,y1)..(x2,y2)) = P[x2][y2] - P[x1-1][y2] - P[x2][y1-1] + P[x1-1][y1-1]

3. Prefix Sums on Trees​

Trees don’t have a linear order, but you can extend prefix sums with DFS orderings:

  • Root-to-node sums: Precompute sum[node] = sum[parent] + value[node] during DFS.

  • Path queries: If you want the sum along path (u,v), use LCA (Lowest Common Ancestor):

    sum(u..v) = sum[root..u] + sum[root..v] - 2 * sum[root..lca(u,v)] + value[lca(u,v)]

  • Subtree sums: Run DFS and assign entry/exit times to nodes (in[node], out[node]). Store prefix sums in Euler tour order to answer “sum of a subtree” in O(1).

4. Generalizations​

Prefix sums aren’t limited to addition:

  • Prefix XORs: Used in problems like “count subarrays with XOR = k”.
  • Prefix Products: Used in modular arithmetic or probability computations.
  • Prefix Max/Min: Sometimes useful (though less common than sum).
  • Higher Dimensions: 3D prefix sums for volumetric queries.

5. Use Cases​

Arrays​

  • Range sum queries (sum(l..r) in O(1)).
  • Find number of subarrays with sum = k (prefix sum + hashmap).
  • Sliding window optimizations.
  • Balance problems (prefix sums for “more 0s or 1s seen so far”).

Matrices​

  • Submatrix sum queries (image processing, 2D range queries).
  • Dynamic programming optimizations (counting paths, grid sums).

Strings​

  • Character frequencies in substrings (freq[c][i] = count of c up to i).
  • Palindrome checking (comparing counts over intervals).

Trees​

  • Root-to-node and path sum queries.
  • Subtree aggregates in O(1) using Euler tour + prefix sums.
  • Dynamic programming over trees (propagating parent state downward).

Graphs & Other Structures​

  • Prefix sums on DFS order for fast reachability / subtree properties.
  • Fenwick Trees & Segment Trees can be seen as dynamic prefix sum structures.

6. Complexity Trade-offs​

  • Static arrays: Prefix sums are optimal.
  • Dynamic arrays (updates): Use Fenwick Tree (BIT) or Segment Tree for prefix sums with updates.
  • Higher dimensions: Complexity grows with space usage (2D = O(n²), 3D = O(n³)) but queries stay O(1).

7. Practice Tasks​

  1. Build prefix sum for array & answer queries.
  2. Submatrix sum queries in O(1).
  3. Count subarrays with sum = k using prefix sums + hashmap.
  4. Use prefix XOR to count subarrays with XOR = k.
  5. Compute subtree sums in a tree using DFS + prefix sums.
  6. Apply prefix sums in a DP optimization (e.g., knapsack row rolling).