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

> Learn how prefix sums optimize array range queries achieving O(1) range sums after O(n) preprocessing. Discover constant-time lookups with simple subtraction.

- Repository: [DonglaiFu/fucking-algorithm](https://github.com/labuladong/fucking-algorithm)
- Tags: tutorial
- Published: 2026-02-25

---

**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:

```java
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:

```java
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:

```java
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:

```java
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:

```java
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:

```java
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.