How Prefix Sums Optimize Array Range Queries: O(1) Range Sum with O(n) Preprocessing

Prefix sums reduce range sum queries from O(n) to O(1) by precomputing cumulative totals, enabling constant-time lookups via simple subtraction.

Prefix sums (also called cumulative sums) are a fundamental algorithmic technique that transforms linear-time range queries into constant-time operations. According to the labuladong/fucking-algorithm repository, specifically in 算法思维系列/前缀和技巧.md, this method precomputes an auxiliary array to store running totals, making it ideal for static arrays with frequent range sum queries.

One-Dimensional Prefix Sum Implementation

In the 1-D case, we construct an auxiliary array preSum where preSum[i] represents the sum of all elements from the start up to (but not including) index i. As implemented in 算法思维系列/前缀和技巧.md (lines 53-71), the construction follows the recurrence:

preSum[i] = preSum[i-1] + nums[i-1]

with the base case preSum[0] = 0.

Building the Prefix Array

The preprocessing step iterates once through the input array to populate the preSum array. This requires O(n) time and O(n) additional space.

O(1) Range Sum Queries

Once built, the sum of any closed interval [left, right] computes in constant time using:

sum = preSum[right+1] - preSum[left]

This subtraction eliminates the need to iterate through the range elements, dropping the query complexity from O(n) to O(1).

The following implementation from the repository demonstrates the LeetCode 304 pattern:

class NumArray {
    private final int[] preSum;

    public NumArray(int[] nums) {
        preSum = new int[nums.length + 1];
        for (int i = 1; i < preSum.length; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
    }

    public int sumRange(int left, int right) {
        return preSum[right + 1] - preSum[left];
    }
}

Two-Dimensional Prefix Sum Matrices

For matrix range queries, the technique extends to two dimensions. The labuladong/fucking-algorithm source code demonstrates this in 算法思维系列/前缀和技巧.md (lines 30-52) using a 2-D preSum matrix where preSum[i][j] stores the sum of the sub-matrix from (0,0) to (i-1, j-1).

Constructing the 2D Prefix Matrix

The build formula accounts for overlapping regions using inclusion-exclusion:

preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] 
             + matrix[i-1][j-1] - preSum[i-1][j-1]

This preprocessing requires O(m·n) time for an m×n matrix.

Rectangle Sum Queries

To obtain the sum of any rectangle defined by [x1, y1, x2, y2] (inclusive), apply the inclusion-exclusion principle:

sum = preSum[x2+1][y2+1] - preSum[x1][y2+1] 
    - preSum[x2+1][y1] + preSum[x1][y1]

Like the 1-D version, this query executes in O(1) time after the preprocessing step.

The complete implementation for 2-D range queries follows the LeetCode 304 structure:

class NumMatrix {
    private final int[][] preSum;

    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        if (m == 0 || n == 0) {
            preSum = new int[0][0];
            return;
        }
        preSum = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1]
                             + matrix[i - 1][j - 1] - preSum[i - 1][j - 1];
            }
        }
    }

    public int sumRegion(int x1, int y1, int x2, int y2) {
        return preSum[x2 + 1][y2 + 1]
               - preSum[x1][y2 + 1]
               - preSum[x2 + 1][y1]
               + preSum[x1][y1];
    }
}

Complexity Trade-offs and Limitations

While prefix sums optimize query performance, they impose specific constraints on mutable data.

Preprocessing vs. Query Costs

• 1-D Arrays: O(n) preprocessing time, O(1) query time, O(n) space
• 2-D Matrices: O(m·n) preprocessing time, O(1) query time, O(m·n) space

When to Avoid Prefix Sums

As noted in 算法思维系列/前缀和技巧.md (lines 78-83), prefix sums are unsuitable for dynamic arrays that change after construction. Each update requires rebuilding the entire prefix structure, costing O(n) for 1-D or O(m·n) for 2-D. For mutable data, prefer segment trees or binary indexed trees (Fenwick trees) which provide O(log n) update and query times.

Summary

• Prefix sums transform O(n) range sum queries into O(1) operations through O(n) preprocessing.
• The technique extends to 2-D matrices using inclusion-exclusion principles for submatrix queries.
• Implementation requires storing an auxiliary array of size n+1 (1-D) or (m+1)×(n+1) (2-D).
• Avoid prefix sums for frequently updated arrays; use segment trees or binary indexed trees instead.
• The labuladong/fucking-algorithm repository provides reference implementations in 算法思维系列/前缀和技巧.md for both LeetCode 303 and 304 patterns.

Frequently Asked Questions

What is the time complexity of building a prefix sum array?

Building a prefix sum array requires a single pass through the input data, resulting in O(n) time complexity for one-dimensional arrays and O(m·n) for two-dimensional matrices. This preprocessing step occurs once before any queries are executed.

Can prefix sums handle dynamic updates to the array?

No, standard prefix sums are static data structures. If the underlying array changes after construction, updating the prefix sum array requires O(n) time for 1-D or O(m·n) for 2-D, effectively eliminating the query performance benefit. For dynamic scenarios, segment trees or binary indexed trees are the preferred alternatives.

How do you calculate the sum of a submatrix using prefix sums?

Given a 2-D prefix sum matrix, calculate the sum of rectangle [x1, y1, x2, y2] using the inclusion-exclusion formula: preSum[x2+1][y2+1] - preSum[x1][y2+1] - preSum[x2+1][y1] + preSum[x1][y1]. This constant-time operation requires four array lookups and two subtractions plus one addition.

What is the space overhead of using prefix sums?

Prefix sums require O(n) additional space for one-dimensional arrays and O(m·n) for two-dimensional matrices. The auxiliary array typically uses an extra row and column (size n+1 or (m+1)×(n+1)) to simplify boundary condition handling and avoid index out-of-bounds checks.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}