Prefix/Suffix Aggregates & 2D Prefix Sum

Many array questions ask about "everything to my left" and "everything to my right": the sum on each side of a pivot, the tallest wall on each side of a cell, the product of every other element. Precompute those aggregates once in a left-to-right and a right-to-left pass, and each index becomes an $O(1)$ lookup. The same idea in two dimensions gives constant-time sub-rectangle sums.

The idea#

A prefix array stores the aggregate of nums[0..i]; a suffix array stores the aggregate of nums[i..n-1]. This works for any associative operation (one where grouping doesn't change the result), not only +: max, min, product, OR, AND and gcd all combine left-to-right the same way.

With both arrays built, "everything except index i" is prefix[i-1] ⊕ suffix[i+1]. You never need an inverse operation, which matters for OR, max or product with zeros, where you can't "subtract" an element back out.

When a running value is enough, you don't need the arrays at all. A single variable for "max so far" or "min so far" in one direction, and one in the other direction, often gives the same answer in $O(1)$ space.

How to spot it#

The cues all mention a side of the index, or "everyone but me". Look for these:

"Strictly to the left / strictly to the right of the index."
"Every element except this one" (product, OR, sum).
Water, light or visibility that depends on the tallest thing on each side.
"Out of order" means something larger to the left or smaller to the right.
Many rectangle-sum queries on a fixed grid.

Template#

This pseudocode builds "everything except index i" for any associative op with an identity value (the value that changes nothing: 0 for +, 1 for *).

pre = list of n + 1 identity values      # pre[i] = op over items[:i]
suf = list of n + 1 identity values      # suf[i] = op over items[i:]
for i from 0 to n - 1:
    pre[i + 1] = op(pre[i], items[i])
for i from n - 1 down to 0:
    suf[i] = op(suf[i + 1], items[i])
for each i:
    out[i] = op(pre[i], suf[i + 1])      # everyone except i
return out

Both passes are $O(n)$ . The extra leading slot makes "everything before i" equal to pre[i].

2D prefix sum#

The same precompute-once idea extends to two dimensions. Some problems ask for many sub-rectangle sums on a fixed matrix. Summing row by row costs $O(\text{rows})$ per query. Instead, let P[r][c] be the sum of the rectangle from (0, 0) up to but not including (r, c). The padding row and column of zeros remove every edge case.

A grid split into four regions: A is the top-left corner, B the strip above the query, C the strip left of it, and D the query rectangle in the bottom-right; D equals the whole prefix minus (A+B) minus (A+C) plus A

The query rectangle D is the whole prefix up to its bottom-right corner, minus the block above it, minus the block to its left. The top-left corner A was subtracted twice, so add it back once. That's inclusion–exclusion, and in code it gives a build step and a four-term query:

P = (rows + 1) x (cols + 1) table of zeros   # row 0 and col 0 stay 0
for each cell (r, c):
    P[r+1][c+1] = cell + P[r][c+1] + P[r+1][c] - P[r][c]

sum of rectangle (r1, c1) to (r2, c2), inclusive:
    P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

Building the table uses the same inclusion–exclusion in reverse: the cell itself, plus the block above, plus the block to the left, minus their overlap.

Pitfalls#

These are the mistakes that most often cost a correct answer.

Inclusive or exclusive? Decide whether prefix[i] includes nums[i]. An extra leading slot (n + 1 entries) makes "everything before i" equal to pre[i].
The add-back term. Forgetting + P[r1][c1] in the 2D query subtracts the top-left corner twice.
Row-by-row isn't 2D. Precomputing per-row prefix sums still costs $O(\text{rows})$ per query. The table above is $O(1)$ .
Sum-only shortcuts. total - nums[i] works for sums, but there is no "un-OR" or "un-max". Use prefix and suffix arrays for those.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first two.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Find Pivot Index

The left sum and the right sum must be equal. You do not need two arrays: the right sum is total - left - nums[i].

Hint: Product of Array Except Self

This is the exclude-one template with multiplication and identity 1. It needs no division, so zeros cause no trouble.

Hint: Maximum OR

Doubling is a left shift, and you should put all k shifts on one element. Let h be the highest set bit among all elements: an element with top bit h and all k shifts sets bit h + k, which no split of the shifts can reach. So try each i with the OR of everyone else from prefix and suffix OR arrays. The answer is max(pre_or[i] | (nums[i] << k) | suf_or[i+1]).

Hint: Shifting Letters

shifts[i] shifts the first i + 1 letters, so letter i moves by the sum of shifts[i:]. Build that suffix sum from the right and apply % 26.

Hint: Shortest Unsorted Continuous Subarray

An index is out of order if something larger exists to its left or something smaller to its right. Prefix-max and suffix-min arrays check that in $O(n)$ (sorting a copy is the $O(n \log n)$ baseline). To drop the arrays, scan left to right with a running max: the last index where nums[i] < running_max is the right end. Mirror it from the right with a running min to find the left end.

Hint: Increasing Triplet Subsequence

Use running extremes. Keep the smallest value seen and the smallest value that has something smaller before it. Any number bigger than both completes a triplet.

Hint: Trapping Rain Water

The water above cell i is min(left_max[i], right_max[i]) - height[i], where both maxima include the cell itself. One prefix-max pass, one suffix-max pass and one sum.

Hint: Range Sum Query 2D - Immutable

Build the padded 2D table once in the constructor. Each query is then the four-term inclusion–exclusion formula.

Hint: Matrix Block Sum

Each answer cell is the sum of a rectangle around it. Clamp the rectangle's corners to the grid, then use the 2D query.

Key takeaways#

Prefix and suffix arrays work for any associative operation: sum, max, min, product, OR.
"Everything except i" is pre[i] ⊕ suf[i+1], with no inverse operation needed.
A running variable often replaces the arrays when you only need one value per direction.
2D sub-rectangle sum = whole − top − left + corner, on a table padded with a zero row and column.
Decide up front whether each prefix entry includes its own index.

Core idea#

Precompute what lies left and right of each index in two passes, so each index becomes an $O(1)$ lookup. In two dimensions, a padded prefix table gives $O(1)$ sub-rectangle sums.

Key points#

Prefix and suffix arrays work for any associative operation: sum, max, min, product, OR, AND, gcd.
"Everything except i" is pre[i] ⊕ suf[i + 1]. No inverse operation is needed.
That matters for OR, max, or product with zeros. You cannot "subtract" those back out.
A running variable per direction often replaces the arrays and gives $O(1)$ space.
Spot it: "strictly to the left / right", "every element except this one", tallest wall on each side, many rectangle-sum queries.

Common variants#

Problem	Trick
Find Pivot Index	Right sum is `total - left - nums[i]`
Product of Array Except Self	Exclude-one with `*` and identity 1
Maximum OR	Put all `k` shifts on one element; try each with prefix/suffix OR
Shortest Unsorted Subarray	Last `nums[i] < running_max` is the right end; mirror for the left
Trapping Rain Water	`min(left_max[i], right_max[i]) - height[i]`

Template#

pre = list of n + 1 identity values      # pre[i] = op over items[:i]
suf = list of n + 1 identity values      # suf[i] = op over items[i:]
for i from 0 to n - 1:
    pre[i + 1] = op(pre[i], items[i])
for i from n - 1 down to 0:
    suf[i] = op(suf[i + 1], items[i])
out[i] = op(pre[i], suf[i + 1]) for each i

2D prefix sum#

P[r][c] is the sum of matrix[0..r-1][0..c-1]. Row 0 and column 0 are zeros.
Build: P[r+1][c+1] = cell + P[r][c+1] + P[r+1][c] - P[r][c].
Query: P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1].
This is inclusion–exclusion: whole − top − left + corner.

Pitfalls#

Inclusive or exclusive? Decide whether prefix[i] includes nums[i]. An extra leading slot helps.
Forgetting + P[r1][c1]. The corner is then subtracted twice.
Per-row prefix sums. They still cost $O(\text{rows})$ per query.
total - nums[i] works only for sums. There is no "un-OR" or "un-max".

Say it in an interview#

"Everything except i is prefix of i combined with suffix of i plus one, so no inverse is needed."
"A rectangle sum is whole minus top minus left plus the corner."