Skip to main content
Talentd

Range Sum Query 2D - Immutable - Solution & Explanation

MediumArrayDesignMatrixPrefix Sum22 min readAsked at: Amazon, Microsoft, Meta +7
Practice this problem

Problem Statement

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

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

Implement the NumMatrix class:

  • NumMatrix(int[][] matrix) Initializes the object with the integer matrix matrix.
  • int sumRegion(int row1, int col1, int row2, int col2) Returns the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

You must design an algorithm where sumRegion works on O(1) time complexity.

 

Example 1:

Input
["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]
[[[[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]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]
Output
[null, 8, 11, 12]

Explanation
NumMatrix numMatrix = new NumMatrix([[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]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (i.e sum of the red rectangle)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (i.e sum of the green rectangle)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (i.e sum of the blue rectangle)

 

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 200
  • -104 <= matrix[i][j] <= 104
  • 0 <= row1 <= row2 < m
  • 0 <= col1 <= col2 < n
  • At most 104 calls will be made to sumRegion.

Approach Overview

Problem Overview: You receive a 2D matrix and must repeatedly return the sum of elements inside a rectangular region defined by (row1, col1) and (row2, col2). The matrix never changes, but the number of queries can be large. A naive sum per query is too slow, so the goal is to preprocess the matrix so each query runs in constant time.

Approach 1: Using 2D Prefix Sum (Preprocessing O(m*n), Query O(1))

This approach builds a cumulative sum matrix where each cell stores the total of all elements from the top-left corner to that position. During preprocessing, iterate through the matrix and compute prefix[i][j] using values from the top, left, and top-left diagonal. Once built, any submatrix sum can be computed using the inclusion–exclusion principle: subtract the extra regions above and left, then add back the overlapping corner. Query computation becomes a few constant-time arithmetic operations. Time complexity is O(m*n) to build the prefix matrix and O(1) per query, with O(m*n) extra space. This technique is a standard extension of prefix sum applied to a matrix and works well when the matrix is immutable and queries are frequent.

Approach 2: 2D Fenwick Tree (Binary Indexed Tree) (Update O(log m * log n), Query O(log m * log n))

A 2D Fenwick Tree stores partial sums in a structured tree-like array that supports efficient region queries. Each update propagates through index ranges using bit manipulation, and prefix sums are computed by traversing parent nodes. A rectangular sum query is derived by combining four prefix queries, similar to the prefix-sum inclusion–exclusion formula. Query and update operations both run in O(log m * log n) time with O(m*n) space. Even though the original problem is immutable, this structure becomes valuable if the matrix supports updates. It relies on concepts from array indexing and tree-based cumulative structures.

Recommended for interviews: The expected solution is the 2D Prefix Sum approach. Interviewers want to see that you recognize repeated range queries and convert them into a preprocessing problem. Building the prefix matrix shows understanding of cumulative sums and inclusion–exclusion logic. Mentioning a 2D Fenwick Tree demonstrates deeper knowledge of data structures for mutable range queries, but implementing it is usually unnecessary unless updates are part of the problem.

Approach 1: Approach 1: Using 2D Prefix Sum

This approach involves preprocessing the matrix to build a prefix sum array. The prefix sum at any index (i, j) in this array contains the sum of elements from (0, 0) to (i, j). With this preprocessed information, calculating any submatrix sum becomes feasible in constant time using the inclusion-exclusion principle.

For a query with corners (row1, col1) and (row2, col2), compute the sum using:

  • Sum of elements from (0,0) to (row2,col2)
  • Subtract areas that are not part of the required rectangle
  • Adjust with intersections if need be

In the C implementation, a 2D prefix sum array is created during initialization. The sum is calculated by adding and subtracting precomputed values from this 2D array.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n) for construction, O(1) for each query.
Space Complexity: O(m * n) for the prefix sum storage.

Try this approach in the editor →

Approach 2: Approach 2: Using Fenwick Tree (Binary Indexed Tree) 2D

This approach involves using a 2D Fenwick Tree to update and query the matrix sums efficiently. Fenwick Trees provide a structure that allows for querying prefix sums, updating values, and hence facilitating the calculation of region sums after updates.

This C++ solution makes use of a 2D Fenwick Tree which is efficient for both point updates and querying prefix sums, making it feasible to handle dynamic updation scenarios.

Code

C++Java

C++

Java

Complexity

Time Complexity: O(log m * log n) per update or query.
Space Complexity: O(m * n) for the tree structure.

Try this approach in the editor →

Approach 3: Two-dimensional Prefix Sum

We use s[i + 1][j + 1] to represent the sum of all elements in the upper left part of the ith row and jth column, where indices i and j both start from 0. We can get the following prefix sum formula:

$ s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + nums[i][j]

Then, the sum of the elements of the rectangle with (x_1, y_1) and (x_2, y_2) as the upper left corner and lower right corner respectively is:

s[x_2 + 1][y_2 + 1] - s[x_2 + 1][y_1] - s[x_1][y_2 + 1] + s[x_1][y_1]

In the initialization method, we preprocess the prefix sum array s, and in the query method, we directly return the result of the above formula.

The time complexity for initializing is O(m times n), and the time complexity for querying is O(1). The space complexity is O(m times n)$.

Code

PythonJavaC++GoTypeScriptRustJavaScriptKotlin

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Kotlin

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Using 2D Prefix Sum

Time Complexity: O(m * n) for construction, O(1) for each query.
Space Complexity: O(m * n) for the prefix sum storage.

Approach 2: Using Fenwick Tree (Binary Indexed Tree) 2D

Time Complexity: O(log m * log n) per update or query.
Space Complexity: O(m * n) for the tree structure.

Two-dimensional Prefix Sum—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
2D Prefix SumPreprocess: O(m*n)
Query: O(1)		O(m*n)Best choice when the matrix is immutable and many range sum queries are expected
2D Fenwick Tree (Binary Indexed Tree)Update: O(log m * log n)
Query: O(log m * log n)		O(m*n)Useful when the matrix can change and you still need fast region sum queries

Video Solution

Range Sum Query 2D - Immutable - Leetcode 304 - Python • NeetCode • 82,833 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Range Sum Query 2D - Immutable easy or hard?
The problem is rated Medium because it requires recognizing the prefix sum pattern in two dimensions. Once the 2D cumulative formula is understood, the implementation is straightforward and commonly used in matrix query problems.
Range Sum Query 2D - Immutable Python/Java solution
Most implementations build a prefix matrix in the constructor and answer queries in a method like sumRegion(). The logic is identical across Python, Java, C++, JavaScript, and C#. Only syntax differs while the algorithm remains O(m*n) preprocessing and O(1) query time.
What is the best approach for Range Sum Query 2D - Immutable?
The optimal solution uses a 2D Prefix Sum matrix. Precompute cumulative sums for every cell so each query can be answered using inclusion–exclusion. This preprocessing takes O(m*n) time and space, while each range sum query runs in O(1).
Is Range Sum Query 2D - Immutable asked at Google/Amazon/Meta?
Range query problems with prefix sums appear frequently in interviews at companies like Google, Amazon, and Meta. Variants include 1D range sums, mutable arrays, and matrix sum queries. Interviewers use these problems to test preprocessing strategies and space-time tradeoffs.
What data structure is used in Range Sum Query 2D - Immutable?
The main data structure is a 2D Prefix Sum array that stores cumulative sums for fast region queries. Advanced variants may use a 2D Fenwick Tree (Binary Indexed Tree) or Segment Tree when updates are allowed.
What is the time complexity of Range Sum Query 2D - Immutable?
Using the optimal 2D prefix sum technique, preprocessing the matrix takes O(m*n). After that, each submatrix sum query runs in constant O(1) time. Space complexity is also O(m*n) for the prefix matrix.
How to solve Range Sum Query 2D - Immutable in O(1) query time?
Precompute a 2D prefix sum array where each cell stores the sum of elements from (0,0) to (i,j). For a query rectangle, combine four prefix values using the inclusion–exclusion formula. This converts every query into a constant-time calculation.

Ready to solve this problem?

Practice Range Sum Query 2D - Immutable with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find the Grid of Region Average

Next

Range Sum Query 2D - Mutable