LeetCode Pattern/Prefix Sum/2D Prefix Sum: Matrix Range Queries in O(1) Time

2D Prefix Sum: Matrix Range Queries in O(1) Time

LeetCopilot Team

Dec 22, 2025

14 min read

Prefix Sum2D MatrixRange QueriesTemplatesInterview Prep

Master 2D prefix sum for matrix range queries. Learn the inclusion-exclusion principle, templates in three languages, and how to avoid off-by-one errors in 2D indexing.

Complete Guide

The Complete Prefix Sum Guide: Master All Patterns, Templates, and Techniques

The ultimate comprehensive guide to prefix sum. Learn all variants (1D, 2D, hash map combinations), when to use each pattern, complete templates in multiple languages, and a systematic approach to solve any prefix sum problem.

Read the complete guide

The 2D prefix sum is the matrix extension of the 1D prefix sum pattern. It transforms O(rows × cols) rectangle sum queries into O(1) lookups.

You've mastered 1D prefix sum. Now imagine applying the same logic to matrices: precompute cumulative sums to answer "what's the sum of this rectangle?" in constant time.

This pattern appears in matrix problems, image processing, and computational geometry. It's a favorite in interviews because it tests your ability to extend 1D thinking to 2D.

This guide will teach you the 2D prefix sum technique, the inclusion-exclusion principle, complete templates, and how to avoid the indexing mistakes that cause wrong answers.

TL;DR

Use 2D prefix sum when:

Need to answer multiple rectangle sum queries on a static matrix
Want O(1) query time after O(rows × cols) preprocessing
Matrix doesn't change between queries

Template:

python

# Build 2D prefix sum (with padding)
prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
for r in range(1, rows + 1):
    for c in range(1, cols + 1):
        prefix[r][c] = (
            matrix[r-1][c-1] +
            prefix[r-1][c] +
            prefix[r][c-1] -
            prefix[r-1][c-1]
        )

# Query rectangle sum in O(1)
sum_rect = (
    prefix[row2+1][col2+1] -
    prefix[row1][col2+1] -
    prefix[row2+1][col1] +
    prefix[row1][col1]
)

Time: O(rows × cols) preprocessing, O(1) per query
Space: O(rows × cols)

What Is 2D Prefix Sum?

Extending 1D to 2D

In 1D, prefix[i] stores the sum of elements from index 0 to i-1.

In 2D, prefix[r][c] stores the sum of all elements in the rectangle from (0,0) to (r-1, c-1).

Visual example:

code

Matrix:
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]

2D Prefix (with padding):
[0,  0,  0,  0]
[0,  1,  3,  6]
[0,  5, 12, 21]
[0, 12, 27, 45]

prefix[2][2] = 12 means:
  Sum of rectangle from (0,0) to (1,1)
  = 1 + 2 + 4 + 5 = 12 ✓

The Inclusion-Exclusion Principle

To calculate the sum of a rectangle, we use the inclusion-exclusion principle:

Building the prefix sum:

code

prefix[r][c] = 
    matrix[r-1][c-1] +     // Current cell
    prefix[r-1][c] +       // Rectangle above
    prefix[r][c-1] -       // Rectangle to the left
    prefix[r-1][c-1]       // Subtract overlap (counted twice)

Querying a rectangle:

code

sum(row1, col1, row2, col2) =
    prefix[row2+1][col2+1] -  // Large rectangle
    prefix[row1][col2+1] -    // Subtract top
    prefix[row2+1][col1] +    // Subtract left
    prefix[row1][col1]        // Add back corner (subtracted twice)

Visual Proof

Building prefix[2][2]:

code

Matrix:
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]

Want: prefix[2][2] = sum of rectangle (0,0) to (1,1)

prefix[2][2] = 
    matrix[1][1] +      // 5
    prefix[1][2] +      // 3 (sum of [1,2])
    prefix[2][1] +      // 5 (sum of [1,4])
    - prefix[1][1]      // -1 (overlap, counted in both above)
    
    = 5 + 3 + 5 - 1 = 12 ✓

Verify: 1 + 2 + 4 + 5 = 12 ✓

Querying rectangle (1,1) to (2,2):

code

Want: sum of [5,6,8,9]

sum = 
    prefix[3][3] -      // 45 (entire matrix)
    prefix[1][3] -      // 6 (top row)
    prefix[3][1] +      // 12 (left column)
    prefix[1][1]        // 1 (corner, subtracted twice)
    
    = 45 - 6 - 12 + 1 = 28 ✓

Verify: 5 + 6 + 8 + 9 = 28 ✓

The Universal Template

Python Template

python

class NumMatrix:
    """
    2D prefix sum for matrix range queries.
    
    Time Complexity:
        - __init__: O(rows × cols)
        - sumRegion: O(1)
    
    Space Complexity: O(rows × cols)
    """
    def __init__(self, matrix: List[List[int]]):
        if not matrix or not matrix[0]:
            self.prefix = [[]]
            return
        
        rows, cols = len(matrix), len(matrix[0])
        # Pad with extra row and column of zeros
        self.prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
        
        # Build 2D prefix sum using inclusion-exclusion
        for r in range(1, rows + 1):
            for c in range(1, cols + 1):
                self.prefix[r][c] = (
                    matrix[r-1][c-1] +       # Current cell
                    self.prefix[r-1][c] +    # Above
                    self.prefix[r][c-1] -    # Left
                    self.prefix[r-1][c-1]    # Overlap
                )
    
    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        """
        Calculate sum of rectangle from (row1, col1) to (row2, col2) inclusive.
        
        Returns:
            Sum of all elements in the rectangle
        """
        return (
            self.prefix[row2+1][col2+1] -
            self.prefix[row1][col2+1] -
            self.prefix[row2+1][col1] +
            self.prefix[row1][col1]
        )

# Usage
matrix = [
    [3, 0, 1, 4, 2],
    [5, 6, 3, 2, 1],
    [1, 2, 0, 1, 5],
    [4, 1, 0, 1, 7],
    [1, 0, 3, 0, 5]
]
obj = NumMatrix(matrix)
print(obj.sumRegion(2, 1, 4, 3))  # Sum of rectangle
print(obj.sumRegion(1, 1, 2, 2))  # Sum of rectangle

JavaScript Template

javascript

class NumMatrix {
    /**
     * @param {number[][]} matrix
     */
    constructor(matrix) {
        if (!matrix || !matrix.length || !matrix[0].length) {
            this.prefix = [[]];
            return;
        }
        
        const rows = matrix.length, cols = matrix[0].length;
        this.prefix = Array(rows + 1).fill(0)
            .map(() => Array(cols + 1).fill(0));
        
        for (let r = 1; r <= rows; r++) {
            for (let c = 1; c <= cols; c++) {
                this.prefix[r][c] = 
                    matrix[r-1][c-1] +
                    this.prefix[r-1][c] +
                    this.prefix[r][c-1] -
                    this.prefix[r-1][c-1];
            }
        }
    }
    
    /**
     * @param {number} row1
     * @param {number} col1
     * @param {number} row2
     * @param {number} col2
     * @return {number}
     */
    sumRegion(row1, col1, row2, col2) {
        return (
            this.prefix[row2+1][col2+1] -
            this.prefix[row1][col2+1] -
            this.prefix[row2+1][col1] +
            this.prefix[row1][col1]
        );
    }
}

Java Template

java

class NumMatrix {
    private int[][] prefix;
    
    public NumMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            prefix = new int[0][0];
            return;
        }
        
        int rows = matrix.length, cols = matrix[0].length;
        prefix = new int[rows + 1][cols + 1];
        
        for (int r = 1; r <= rows; r++) {
            for (int c = 1; c <= cols; c++) {
                prefix[r][c] = 
                    matrix[r-1][c-1] +
                    prefix[r-1][c] +
                    prefix[r][c-1] -
                    prefix[r-1][c-1];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return 
            prefix[row2+1][col2+1] -
            prefix[row1][col2+1] -
            prefix[row2+1][col1] +
            prefix[row1][col1];
    }
}

Pattern: Range Sum Query 2D - Immutable

Problem (LeetCode #304)

Given a 2D matrix, handle multiple queries of the following type:

Calculate the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Example:

code

Matrix:
[3, 0, 1, 4, 2]
[5, 6, 3, 2, 1]
[1, 2, 0, 1, 5]
[4, 1, 0, 1, 7]
[1, 0, 3, 0, 5]

Query: sumRegion(2, 1, 4, 3)
Rectangle from (2,1) to (4,3):
[2, 0, 1]
[1, 0, 1]
[0, 3, 0]
Sum = 2 + 0 + 1 + 1 + 0 + 1 + 0 + 3 + 0 = 8

Solution

python

class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        if not matrix or not matrix[0]:
            self.prefix = [[]]
            return
        
        rows, cols = len(matrix), len(matrix[0])
        self.prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
        
        for r in range(1, rows + 1):
            for c in range(1, cols + 1):
                self.prefix[r][c] = (
                    matrix[r-1][c-1] +
                    self.prefix[r-1][c] +
                    self.prefix[r][c-1] -
                    self.prefix[r-1][c-1]
                )
    
    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return (
            self.prefix[row2+1][col2+1] -
            self.prefix[row1][col2+1] -
            self.prefix[row2+1][col1] +
            self.prefix[row1][col1]
        )

Complexity Analysis

Time:

Constructor: O(rows × cols) to build prefix matrix
sumRegion: O(1) per query
Total for q queries: O(rows × cols + q)

Space: O(rows × cols) for prefix matrix

Comparison with brute force:

Brute force: O(q × rows × cols) for q queries
2D prefix sum: O(rows × cols + q)
Speedup: Massive when q is large

Pattern: Matrix Block Sum

Problem (LeetCode #1314)

Given a matrix and an integer k, return a matrix where each element is the sum of all elements in the rectangle defined by (i-k, j-k) to (i+k, j+k), clamped to matrix boundaries.

Example:

code

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[12,21,16],[27,45,33],[24,39,28]]

Explanation: answer[1][1] = sum of rectangle from (0,0) to (2,2) = 45

Solution

python

def matrixBlockSum(mat: List[List[int]], k: int) -> List[List[int]]:
    """
    Use 2D prefix sum to calculate block sums efficiently.
    Time: O(rows × cols), Space: O(rows × cols)
    """
    rows, cols = len(mat), len(mat[0])
    
    # Build 2D prefix sum
    prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
    for r in range(1, rows + 1):
        for c in range(1, cols + 1):
            prefix[r][c] = (
                mat[r-1][c-1] +
                prefix[r-1][c] +
                prefix[r][c-1] -
                prefix[r-1][c-1]
            )
    
    # Calculate block sums
    result = [[0] * cols for _ in range(rows)]
    for r in range(rows):
        for c in range(cols):
            # Clamp boundaries
            r1 = max(0, r - k)
            c1 = max(0, c - k)
            r2 = min(rows - 1, r + k)
            c2 = min(cols - 1, c + k)
            
            # Query rectangle sum
            result[r][c] = (
                prefix[r2+1][c2+1] -
                prefix[r1][c2+1] -
                prefix[r2+1][c1] +
                prefix[r1][c1]
            )
    
    return result

# Test
matrix = [[1,2,3],[4,5,6],[7,8,9]]
k = 1
print(matrixBlockSum(matrix, k))
# [[12,21,16],[27,45,33],[24,39,28]]

Why It Works

For each cell (r, c), we need the sum of a rectangle centered at (r, c) with radius k. Using 2D prefix sum, we can calculate this in O(1) instead of O(k²).

The Inclusion-Exclusion Formula

Why We Add and Subtract

When building the prefix sum:

code

prefix[r][c] = 
    matrix[r-1][c-1] +    // Current cell
    prefix[r-1][c] +      // Rectangle above (includes overlap)
    prefix[r][c-1] -      // Rectangle left (includes overlap)
    prefix[r-1][c-1]      // Subtract overlap (counted twice)

Visual:

code

+-------+---+
|       | A |
|   O   +---+
|       | X |
+-------+---+

O = overlap (prefix[r-1][c-1])
A = above only (prefix[r-1][c] - O)
L = left only (prefix[r][c-1] - O)
X = current cell (matrix[r-1][c-1])

prefix[r][c] = O + A + O + L + X
             = 2O + A + L + X
             
But we want: O + A + L + X

So: prefix[r][c] = (O + A) + (O + L) + X - O
                 = prefix[r-1][c] + prefix[r][c-1] + X - prefix[r-1][c-1]

When Querying

code

sum(row1, col1, row2, col2) =
    prefix[row2+1][col2+1] -  // Entire rectangle from (0,0)
    prefix[row1][col2+1] -    // Subtract top part
    prefix[row2+1][col1] +    // Subtract left part
    prefix[row1][col1]        // Add back corner (subtracted twice)

Visual:

code

+---+-------+
| C |   T   |
+---+-------+
| L |   R   |
|   |       |
+---+-------+

C = corner (prefix[row1][col1])
T = top (prefix[row1][col2+1] - C)
L = left (prefix[row2+1][col1] - C)
R = result rectangle

prefix[row2+1][col2+1] = C + T + L + R

R = prefix[row2+1][col2+1] - (C + T) - (C + L) + C
  = prefix[row2+1][col2+1] - prefix[row1][col2+1] - prefix[row2+1][col1] + prefix[row1][col1]

Edge Cases

1. Empty Matrix

python

matrix = []
obj = NumMatrix(matrix)
# Should not crash

Handling:

python

if not matrix or not matrix[0]:
    self.prefix = [[]]
    return

2. 1×1 Matrix

python

matrix = [[5]]
obj = NumMatrix(matrix)
print(obj.sumRegion(0, 0, 0, 0))  # Should return 5

Trace:

code

prefix = [[0, 0],
          [0, 5]]

sumRegion(0, 0, 0, 0) = 
    prefix[1][1] - prefix[0][1] - prefix[1][0] + prefix[0][0]
    = 5 - 0 - 0 + 0 = 5 ✓

3. Single Row or Column

python

matrix = [[1, 2, 3, 4]]  # Single row
obj = NumMatrix(matrix)
print(obj.sumRegion(0, 1, 0, 2))  # 2 + 3 = 5

Works correctly with padding.

4. Negative Numbers

python

matrix = [[1, -2], [-3, 4]]
obj = NumMatrix(matrix)
print(obj.sumRegion(0, 0, 1, 1))  # 1 + (-2) + (-3) + 4 = 0

2D prefix sum handles negatives perfectly.

Common Mistakes

Mistake 1: Forgetting to Subtract Overlap

❌ Wrong:

python

prefix[r][c] = (
    matrix[r-1][c-1] +
    prefix[r-1][c] +
    prefix[r][c-1]
    # Missing: - prefix[r-1][c-1]
)

Result: Overcounts the overlap region.

✅ Correct:

python

prefix[r][c] = (
    matrix[r-1][c-1] +
    prefix[r-1][c] +
    prefix[r][c-1] -
    prefix[r-1][c-1]  # Subtract overlap
)

See guide: 2D Off-by-One Errors

Mistake 2: Wrong Index Calculation

❌ Wrong:

python

# Query without +1
sum_rect = (
    prefix[row2][col2] -  # Should be row2+1, col2+1
    prefix[row1][col2] -
    prefix[row2][col1] +
    prefix[row1][col1]
)

✅ Correct:

python

sum_rect = (
    prefix[row2+1][col2+1] -
    prefix[row1][col2+1] -
    prefix[row2+1][col1] +
    prefix[row1][col1]
)

Mistake 3: Not Padding the Matrix

❌ Wrong:

python

# No padding, same size as matrix
prefix = [[0] * cols for _ in range(rows)]

Problem: Requires special handling for row1=0 or col1=0.

✅ Correct:

python

# Pad with extra row and column
prefix = [[0] * (cols + 1) for _ in range(rows + 1)]

Mistake 4: Confusing Matrix Indices

❌ Wrong:

python

# Using r, c directly instead of r-1, c-1
prefix[r][c] = matrix[r][c] + ...  # Out of bounds!

✅ Correct:

python

# Offset by 1 due to padding
prefix[r][c] = matrix[r-1][c-1] + ...

When to Use 2D Prefix Sum

✅ Use When:

Multiple rectangle sum queries on a static matrix
Matrix doesn't change between queries
O(rows × cols) space is acceptable
Need O(1) query time

❌ Don't Use When:

Single query only (not worth preprocessing)
Matrix is frequently updated (use 2D segment tree)
Must use O(1) space (can't store prefix matrix)
Finding maximum/minimum in rectangle (different problem)

Complexity Comparison

Problem: Answer q rectangle sum queries on rows × cols matrix.

Approach	Time	Space	When to Use
Brute force	O(q × rows × cols)	O(1)	q = 1
2D prefix sum	O(rows × cols + q)	O(rows × cols)	q ≥ 2
2D segment tree	O(rows × cols + q log(rows × cols))	O(rows × cols)	Frequent updates

Practice Problems

Master 2D prefix sum with these problems:

Beginner:

Range Sum Query 2D - Immutable (#304) - Direct template
Matrix Block Sum (#1314) - Block sums with boundaries

Intermediate:
3. Number of Submatrices That Sum to Target (#1074) - 2D + hash map
4. Max Sum of Rectangle No Larger Than K (#363) - 2D + binary search

Advanced:
5. Count Submatrices With All Ones (#1504) - 2D prefix + DP
6. Largest Submatrix With Rearrangements (#1727) - 2D prefix variant

FAQ

Q: Why do we need padding in 2D prefix sum?

A: Padding simplifies the formula and avoids special cases for rectangles starting at row 0 or column 0. See 2D Off-by-One.

Q: Can I use 2D prefix sum if the matrix has updates?

A: Not efficiently. Each update would require O(rows × cols) to rebuild. Use a 2D segment tree for frequent updates.

Q: How do I remember the inclusion-exclusion formula?

A: Think: "Big rectangle - top part - left part + corner (subtracted twice)."

Q: Does 2D prefix sum work with negative numbers?

A: Yes, perfectly. The formula works for any integer values.

Q: What if the query rectangle is out of bounds?

A: Clamp the coordinates to matrix boundaries before querying, like in Matrix Block Sum.

Conclusion

2D prefix sum extends the 1D pattern to matrices, enabling O(1) rectangle sum queries.

Key principles:

Pad with zeros (extra row and column)
Inclusion-exclusion for building and querying
Formula: prefix[r][c] = matrix + above + left - overlap
Query: sum = large - top - left + corner

The template:

python

# Build
prefix[r][c] = (
    matrix[r-1][c-1] +
    prefix[r-1][c] +
    prefix[r][c-1] -
    prefix[r-1][c-1]
)

# Query
sum = (
    prefix[row2+1][col2+1] -
    prefix[row1][col2+1] -
    prefix[row2+1][col1] +
    prefix[row1][col1]
)

When to use:

Multiple rectangle queries
Static matrix
O(rows × cols) space available

Master this pattern, and you'll solve matrix range query problems with confidence. For more, see the complete prefix sum guide, 1D template, and 2D off-by-one errors.

Next time you see "matrix range sum," reach for 2D prefix sum.

Want to Practice LeetCode Smarter?

LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.

Learn More About LeetCopilot

Add to Chrome for free

Also compatible with Edge, Brave, and Opera

2D Prefix Sum: Matrix Range Queries in O(1) Time

The Complete Prefix Sum Guide: Master All Patterns, Templates, and Techniques

Table of Contents

TL;DR

What Is 2D Prefix Sum?

Extending 1D to 2D

The Inclusion-Exclusion Principle

Visual Proof

The Universal Template

Python Template

JavaScript Template

Java Template

Pattern: Range Sum Query 2D - Immutable

Problem (LeetCode #304)

Solution

Complexity Analysis

Pattern: Matrix Block Sum

Problem (LeetCode #1314)

Solution

Why It Works

The Inclusion-Exclusion Formula

Why We Add and Subtract

When Querying

Edge Cases

1. Empty Matrix

2. 1×1 Matrix

3. Single Row or Column

4. Negative Numbers

Common Mistakes

Mistake 1: Forgetting to Subtract Overlap

Mistake 2: Wrong Index Calculation

Mistake 3: Not Padding the Matrix

Mistake 4: Confusing Matrix Indices

When to Use 2D Prefix Sum

✅ Use When:

❌ Don't Use When:

Complexity Comparison

Practice Problems

FAQ

Conclusion

Want to Practice LeetCode Smarter?

Related Tutorials

Why Your Prefix Sum Has Off-by-One Errors (And How to Fix Them)

The {0: 1} Initialization: Why It's Critical for Subarray Sum

2D Prefix Sum Off-by-One: The Inclusion-Exclusion Mistake