Range Sum Query 2D - Mutable solution and explanation
Google
The problem
Given a 2D matrix matrix, handle multiple queries of the following types:
- Update the value of a cell in
matrix. - Calculate the sum of the elements of
matrixinside 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 matrixmatrix.void update(int row, int col, int val)Updates the value ofmatrix[row][col]to beval.int sumRegion(int row1, int col1, int row2, int col2)Returns the sum of the elements ofmatrixinside 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.lengthn == matrix[i].length1 <= m, n <= 200-1000 <= matrix[i][j] <= 10000 <= row < m0 <= col < n-1000 <= val <= 10000 <= row1 <= row2 < m0 <= col1 <= col2 < n- At most
5000calls will be made tosumRegionandupdate.
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
class BinaryIndexedTree:
def __init__(self, n):
self.n = n
self.c = [0] * (n + 1)
@staticmethod
def lowbit(x):
return x & -x
def update(self, x, delta):
while x <= self.n:
self.c[x] += delta
x += BinaryIndexedTree.lowbit(x)
def query(self, x):
s = 0
while x > 0:
s += self.c[x]
x -= BinaryIndexedTree.lowbit(x)
return s
class NumMatrix:
def __init__(self, matrix: List[List[int]]):
self.trees = []
n = len(matrix[0])
for row in matrix:
tree = BinaryIndexedTree(n)
for j, v in enumerate(row):
tree.update(j + 1, v)
self.trees.append(tree)
def update(self, row: int, col: int, val: int) -> None:
tree = self.trees[row]
prev = tree.query(col + 1) - tree.query(col)
tree.update(col + 1, val - prev)
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
return sum(
tree.query(col2 + 1) - tree.query(col1)
for tree in self.trees[row1 : row2 + 1]
)
# Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix(matrix)
# obj.update(row,col,val)
# param_2 = obj.sumRegion(row1,col1,row2,col2)class BinaryIndexedTree {
private int n;
private int[] c;
public BinaryIndexedTree(int n) {
this.n = n;
c = new int[n + 1];
}
public void update(int x, int delta) {
while (x <= n) {
c[x] += delta;
x += lowbit(x);
}
}
public int query(int x) {
int s = 0;
while (x > 0) {
s += c[x];
x -= lowbit(x);
}
return s;
}
public static int lowbit(int x) {
return x & -x;
}
}
class NumMatrix {
private BinaryIndexedTree[] trees;
public NumMatrix(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
trees = new BinaryIndexedTree[m];
for (int i = 0; i < m; ++i) {
BinaryIndexedTree tree = new BinaryIndexedTree(n);
for (int j = 0; j < n; ++j) {
tree.update(j + 1, matrix[i][j]);
}
trees[i] = tree;
}
}
public void update(int row, int col, int val) {
BinaryIndexedTree tree = trees[row];
int prev = tree.query(col + 1) - tree.query(col);
tree.update(col + 1, val - prev);
}
public int sumRegion(int row1, int col1, int row2, int col2) {
int s = 0;
for (int i = row1; i <= row2; ++i) {
BinaryIndexedTree tree = trees[i];
s += tree.query(col2 + 1) - tree.query(col1);
}
return s;
}
}
/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix obj = new NumMatrix(matrix);
* obj.update(row,col,val);
* int param_2 = obj.sumRegion(row1,col1,row2,col2);
*/class BinaryIndexedTree {
public:
int n;
vector<int> c;
BinaryIndexedTree(int _n)
: n(_n)
, c(_n + 1) {}
void update(int x, int delta) {
while (x <= n) {
c[x] += delta;
x += lowbit(x);
}
}
int query(int x) {
int s = 0;
while (x > 0) {
s += c[x];
x -= lowbit(x);
}
return s;
}
int lowbit(int x) {
return x & -x;
}
};
class NumMatrix {
public:
vector<BinaryIndexedTree*> trees;
NumMatrix(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
trees.resize(m);
for (int i = 0; i < m; ++i) {
BinaryIndexedTree* tree = new BinaryIndexedTree(n);
for (int j = 0; j < n; ++j) tree->update(j + 1, matrix[i][j]);
trees[i] = tree;
}
}
void update(int row, int col, int val) {
BinaryIndexedTree* tree = trees[row];
int prev = tree->query(col + 1) - tree->query(col);
tree->update(col + 1, val - prev);
}
int sumRegion(int row1, int col1, int row2, int col2) {
int s = 0;
for (int i = row1; i <= row2; ++i) {
BinaryIndexedTree* tree = trees[i];
s += tree->query(col2 + 1) - tree->query(col1);
}
return s;
}
};
/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix* obj = new NumMatrix(matrix);
* obj->update(row,col,val);
* int param_2 = obj->sumRegion(row1,col1,row2,col2);
*/type BinaryIndexedTree struct {
n int
c []int
}
func newBinaryIndexedTree(n int) *BinaryIndexedTree {
c := make([]int, n+1)
return &BinaryIndexedTree{n, c}
}
func (this *BinaryIndexedTree) lowbit(x int) int {
return x & -x
}
func (this *BinaryIndexedTree) update(x, delta int) {
for x <= this.n {
this.c[x] += delta
x += this.lowbit(x)
}
}
func (this *BinaryIndexedTree) query(x int) int {
s := 0
for x > 0 {
s += this.c[x]
x -= this.lowbit(x)
}
return s
}
type NumMatrix struct {
trees []*BinaryIndexedTree
}
func Constructor(matrix [][]int) NumMatrix {
n := len(matrix[0])
var trees []*BinaryIndexedTree
for _, row := range matrix {
tree := newBinaryIndexedTree(n)
for j, v := range row {
tree.update(j+1, v)
}
trees = append(trees, tree)
}
return NumMatrix{trees}
}
func (this *NumMatrix) Update(row int, col int, val int) {
tree := this.trees[row]
prev := tree.query(col+1) - tree.query(col)
tree.update(col+1, val-prev)
}
func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
s := 0
for i := row1; i <= row2; i++ {
tree := this.trees[i]
s += tree.query(col2+1) - tree.query(col1)
}
return s
}
/**
* Your NumMatrix object will be instantiated and called as such:
* obj := Constructor(matrix);
* obj.Update(row,col,val);
* param_2 := obj.SumRegion(row1,col1,row2,col2);
*/Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Matrix Scan | Update 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 Tree | Update O(log m * log n), Query O(log m * log n) | O(m*n) | General case with frequent updates and queries |
| 2D Segment Tree | Update O(log m * log n), Query O(log m * log n) | O(m*n) | When you need flexible range operations beyond simple sums |
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.