Past and Future: Mastering Prefix and Suffix Arrays

Most developers learn about range queries when their application slows down under heavy load. By then, calculating the sum of array segments repeatedly in linear time becomes an expensive mistake.

If you know your total sales from January to May, and your total sales from January to February, you don’t add up March, April, and May individually. You subtract the February running tally from the May tally. That simple subtraction is the core of prefix and suffix operations.

The Core Concept: Prefix Sums

A prefix sum array precomputes the cumulative sum of elements from the beginning up to each index. This shifts the cost of querying a contiguous range from linear time to a single subtraction.

For any 1D array, building the prefix array takes linear time:

P[i] = P[i-1] + A[i]

Once built, you calculate the sum of any subarray from index i to j in constant time:

Sum(i, j) = P[j] - P[i-1]

(With 0-based indexing, you typically define P[0] = 0 and store prefix sums at P[i+1], so Sum(i, j) = P[j+1] - P[i].)

Reversible Accumulations

The same pattern applies to any operation that you can reverse or accumulate:

• Prefix XOR tracks bitwise parity because XOR is its own inverse.
• Prefix Product tracks products, though you must handle zeros carefully because division is not always valid.
• Prefix Min/Max track the extreme values seen so far from left to right. They are great for monotone queries like “minimum from the start to i”, but they cannot answer arbitrary range min/max queries in constant time because min and max are not strictly reversible.

Moving to Two Dimensions

For matrices, 2D prefix sums store the sum of all elements in a rectangle from the top-left corner (0, 0) to any cell (i, j).

Define a 2D prefix array P such that:

P[i][j] = sum of all A[r][c] with 0 ≤ r ≤ i and 0 ≤ c ≤ j

You can build this in O(n*m) time using:

P[i][j] = A[i][j]

+ P[i-1][j] (if i > 0)

+ P[i][j-1] (if j > 0)

- P[i-1][j-1] (if i > 0 and j > 0)

Then, by applying the Inclusion–Exclusion principle, you can retrieve the sum of any sub-grid (r1, c1) to (r2, c2) in constant time:

Sum(r1…r2, c1…c2) = P[r2][c2]

- P[r1-1][c2]

- P[r2][c1-1]

+ P[r1-1][c1-1]

This is particularly useful for image processing, heatmaps, or geographic coordinate grids where range queries occur thousands or millions of times per second.

Suffix Sums: Looking Ahead

While prefix arrays accumulate state from left to right, suffix arrays accumulate state backwards from right to left. A suffix array answers a different question: what is the aggregate value of everything remaining in the array from this index onward?

Building a suffix sum array mirrors the prefix process, but starts at the end of the array:

S[i] = A[i] + S[i+1]

By precomputing this right-to-left pass, querying the sum from any index i to the end of the array takes constant time:

Sum(i…n-1) = S[i]

You can similarly define suffix products, suffix XOR, suffix min/max, and so on, whenever you need fast access to “everything to the right” of a position.

Prefix + Suffix: The Ultimate Combo

The synergy of these two approaches emerges when you combine them. By precomputing both passes, you can isolate a single element and instantly query the state of its entire left side and its entire right side simultaneously.

Evaluating Everything Except Self

Consider the classic problem of calculating the product of an array except for the element at the current index, without using division.

Naively, for each index i, you might scan the rest of the array and multiply all elements except A[i]. That leads to O(n^2) time.

By combining a prefix product and a suffix product, you solve the problem in linear time:

• The product of everything to the left of index i is its prefix product.
• The product of everything to the right of index i is its suffix product.

Multiplying these two precomputed values gives the final answer for each index.

You don’t even need secondary arrays to store these intermediate values. You can write the prefix product directly into the output array, and then multiply by the suffix product on the fly in a single backwards pass.

def productExceptSelf(nums):
    n = len(nums)
    answer = [1] * n

    # Accumulate prefix product from left to right
    prefix = 1
    for i in range(n):
        answer[i] = prefix
        prefix *= nums[i]

    # Multiply by suffix product on the fly from right to left
    suffix = 1
    for i in range(n - 1, -1, -1):
        answer[i] *= suffix
        suffix *= nums[i]

    return answer

This pattern generalizes to many “everything except self” problems where the combination operation is associative and you can cheaply maintain running aggregates from both directions.

The Physics of Trapping Water

The two-way dependency also solves the classic trapping rain water problem.

You are given an array height[i] representing the elevation of buildings. The amount of water that can rest on top of any building i depends on:

• The tallest building to its left.
• The tallest building to its right.

The water level above building i is:

water_level[i] = min(max_left[i], max_right[i])

water_at_i = max(0, water_level[i] - height[i])

You can compute max_left with a prefix max pass and max_right with a suffix max pass, then sum water_at_i over all i in linear time.

When to Reach for Prefix and Suffix Arrays

Precomputing cumulative states simplifies dynamic, nested iterations into simple, static lookups.

Use prefix/suffix arrays when:

• You have many queries over a static array or grid.
• The queries involve contiguous ranges (subarrays or sub-rectangles).
• The operation is associative and ideally reversible (for full range flexibility).

In these cases, prefix and suffix arrays often give you:

• O(n) preprocessing time.
• O(1) query time.
• Simple, cache-friendly implementations.

When designing an algorithm that queries continuous ranges, look for reversible operations and cumulative patterns before reaching for more complex tree structures like segment trees or Fenwick trees. If the underlying data is static, accumulating running states might be the only optimization you need.

Your explanation of prefix and suffix arrays is accurate and well-structured. It covers:

• 1D prefix sums and how they reduce range-sum queries to O(1) after O(n) preprocessing.
• Reversible accumulations (sum, XOR, product) vs non-reversible ones (min/max for arbitrary ranges).
• 2D prefix sums and inclusion–exclusion for constant-time sub-rectangle queries.
• Suffix sums/products and their use for right-side aggregates.
• Combining prefix and suffix passes for “everything except self” and Trapping Rain Water.

A few concise, practical takeaways:

1. Use prefix sums when
   • Data is static (no frequent updates).
   • You have many range queries over contiguous segments.
   • The operation is associative and preferably reversible (sum, XOR, product without tricky zeros).
2. Use 2D prefix sums when
   • You query many axis-aligned rectangles (images, heatmaps, grids).
3. Use prefix + suffix when
   • Each position depends on information from both left and right (product-except-self, trapping rain water, visibility problems, etc.).
4. Reach for segment/Fenwick trees instead when
   • The array is updated frequently and you still need fast range queries.

Your mental model—“precompute running state once, then answer queries with simple subtraction/combination”—is exactly the right way to think about these techniques.

class PrefixSum1D:
    def __init__(self, arr):
        n = len(arr)
        self.pref = [0] * (n + 1)
        for i in range(n):
            self.pref[i + 1] = self.pref[i] + arr[i]

    def range_sum(self, l, r):
        """Sum on [l, r], 0-based inclusive."""
        return self.pref[r + 1] - self.pref[l]


class PrefixSum2D:
    def __init__(self, grid):
        if not grid:
            self.ps = [[0]]
            return
        n, m = len(grid), len(grid[0])
        self.ps = [[0] * (m + 1) for _ in range(n + 1)]
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                self.ps[i][j] = (
                    grid[i - 1][j - 1]
                    + self.ps[i - 1][j]
                    + self.ps[i][j - 1]
                    - self.ps[i - 1][j - 1]
                )

    def rect_sum(self, r1, c1, r2, c2):
        """Sum on rectangle [r1..r2], [c1..c2], 0-based inclusive."""
        r1 += 1; c1 += 1; r2 += 1; c2 += 1
        return (
            self.ps[r2][c2]
            - self.ps[r1 - 1][c2]
            - self.ps[r2][c1 - 1]
            + self.ps[r1 - 1][c1 - 1]
        )


def product_except_self(nums):
    n = len(nums)
    ans = [1] * n
    prefix = 1
    for i in range(n):
        ans[i] = prefix
        prefix *= nums[i]
    suffix = 1
    for i in range(n - 1, -1, -1):
        ans[i] *= suffix
        suffix *= nums[i]
    return ans


def trap_rain_water(height):
    n = len(height)
    if n == 0:
        return 0
    max_left = [0] * n
    max_right = [0] * n

    cur = 0
    for i in range(n):
        cur = max(cur, height[i])
        max_left[i] = cur

    cur = 0
    for i in range(n - 1, -1, -1):
        cur = max(cur, height[i])
        max_right[i] = cur

    water = 0
    for i in range(n):
        water += max(0, min(max_left[i], max_right[i]) - height[i])
    return water