Skip to main content
Talentd

Range Sum Query 2D - Mutable - Solution & Explanation

MediumPremiumFree on FleetCodeArrayDesignBinary Indexed TreeSegment Tree7 min readAsked at: Amazon, Google, Bloomberg
Practice this problem

Problem Statement

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

  1. Update the value of a cell in matrix.
  2. 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.
  • void update(int row, int col, int val) Updates the value of matrix[row][col] to be val.
  • 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).

 

Example 1:

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

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 left red rectangle)
numMatrix.update(3, 2, 2); // matrix changes from left image to right image
numMatrix.sumRegion(2, 1, 4, 3); // return 10 (i.e. sum of the right red rectangle)

 

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 200
  • -1000 <= matrix[i][j] <= 1000
  • 0 <= row < m
  • 0 <= col < n
  • -1000 <= val <= 1000
  • 0 <= row1 <= row2 < m
  • 0 <= col1 <= col2 < n
  • At most 5000 calls will be made to sumRegion and update.

Approach Overview

Problem Overview: You need to design a data structure for a 2D matrix that supports two operations: updating a cell value and returning the sum of elements inside any rectangular submatrix. The challenge is handling frequent updates without recomputing sums for the entire region every time.

Approach 1: Brute Force Recalculation (Update O(1), Query O(m*n))

Store the matrix as-is. For every sumRegion(row1, col1, row2, col2) call, iterate through all cells inside the rectangle and accumulate the sum. Updates are trivial because you simply replace the value in the matrix. The downside is query performance: each query scans up to the entire matrix, giving O(m*n) time and O(1) extra space. This approach works for small matrices or when queries are rare.

Approach 2: 2D Prefix Sum with Rebuild (Update O(m*n), Query O(1))

Precompute a prefix sum matrix where each cell stores the sum of the rectangle from (0,0) to that position. A submatrix sum can then be computed using inclusion–exclusion in constant time. However, when a value changes, every affected prefix cell must be recomputed, which costs O(m*n). This approach favors scenarios with many queries but very few updates. It relies heavily on concepts from array traversal and matrix prefix sums.

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

A 2D Binary Indexed Tree maintains cumulative sums in a hierarchical structure. Each update propagates changes to logarithmically many nodes, while queries aggregate prefix sums efficiently. To compute a rectangular region sum, query four prefix regions and combine them using inclusion–exclusion. Both updates and queries run in O(log m * log n) time with O(m*n) space. This structure handles frequent updates and queries efficiently, making it the practical optimal solution.

Approach 4: 2D Segment Tree (Update O(log m * log n), Query O(log m * log n))

A 2D Segment Tree organizes the matrix into nested segment trees across rows and columns. Each node represents the sum of a sub-rectangle. Updates propagate through both tree dimensions, and queries traverse only relevant nodes. Performance matches the Binary Indexed Tree with O(log m * log n) operations, but implementation complexity and memory overhead are higher. This approach is useful when you need flexible range operations beyond simple sums.

Recommended for interviews: Interviewers expect the 2D Binary Indexed Tree solution. The brute force version shows you understand the problem baseline, but the Fenwick Tree demonstrates strong data structure skills and the ability to optimize both updates and queries to logarithmic time.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Matrix ScanUpdate O(1), Query O(m*n)O(1)Small matrices or when queries are very rare
2D Prefix Sum (Rebuild on Update)Update O(m*n), Query O(1)O(m*n)Many queries but almost no updates
2D Binary Indexed TreeUpdate O(log m * log n), Query O(log m * log n)O(m*n)General case with frequent updates and queries
2D Segment TreeUpdate O(log m * log n), Query O(log m * log n)O(m*n)When you need flexible range operations beyond simple sums

Video Solution

Leetcode 308. Range Sum Query 2D - Mutable (binary index tree) • LetsCode • 621 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Range Sum Query 2D - Mutable easy or hard?
Range Sum Query 2D - Mutable is considered a medium difficulty problem. The challenge comes from designing a data structure that supports both efficient updates and fast submatrix queries, typically requiring knowledge of Fenwick Trees or Segment Trees.
Range Sum Query 2D - Mutable Python/Java solution
Most solutions implement a class that stores the matrix and a 2D Binary Indexed Tree. Methods update the difference when a cell value changes and compute prefix sums to derive region sums. The same logic works across Python, Java, C++, and Go with O(log m * log n) operations.
What is the best approach for Range Sum Query 2D - Mutable?
The best approach is a 2D Binary Indexed Tree (Fenwick Tree). It supports both updates and submatrix sum queries in O(log m * log n) time while using O(m*n) space. This structure efficiently maintains cumulative sums and is widely considered the optimal solution for dynamic range sum queries in a matrix.
Is Range Sum Query 2D - Mutable asked at Google/Amazon/Meta?
Range Sum Query problems frequently appear in interviews at large tech companies including Google, Amazon, and Meta. Variants involving segment trees, Fenwick trees, or dynamic range queries are common in system design and algorithm rounds.
What data structure is used in Range Sum Query 2D - Mutable?
The primary data structures used are a 2D Binary Indexed Tree (Fenwick Tree) or a 2D Segment Tree. Both support efficient updates and range queries, but Fenwick Trees are typically preferred because they are simpler to implement with similar logarithmic complexity.
What is the time complexity of Range Sum Query 2D - Mutable?
The optimal solution using a 2D Binary Indexed Tree runs updates and queries in O(log m * log n) time. Brute force queries take O(m*n), while a prefix sum approach provides O(1) queries but requires O(m*n) time for updates.
How to solve Range Sum Query 2D - Mutable in O(log m * log n)?
Use a 2D Binary Indexed Tree to maintain prefix sums across both rows and columns. Each update propagates through the Fenwick Tree in logarithmic steps, and each region query is computed using four prefix sum queries combined with inclusion–exclusion.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Increment Submatrices by One

Next

Range Sum Query 2D - Immutable