Log inSign up
hardLeetCodeNot Started

Range Sum Query 2D - Mutable

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Advanced DSA
Solve on LeetCode
Lesson

Problem Statement

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

1. Update: void update(int row, int col, int val) updates the value of matrix[row][col] to be val. 2. Sum Region: 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) inclusive.

Both update and sumRegion must run efficiently in O(log m \cdot log n) time using a 2D Binary Indexed Tree (2D Fenwick Tree).

Example 1 · 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 (sum of submatrix [2..4]x[1..3]) numMatrix.update(3, 2, 2); // matrix[3][2] updated from 0 to 2 numMatrix.sumRegion(2, 1, 4, 3); // return 10

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 3 distinct approaches for Range Sum Query 2D - Mutable.
  • Implement fully runnable solutions in C++, Java, Python, and JavaScript.
  • Analyze algorithmic trade-offs across data structure designs.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Range Sum Query 2D - Mutable
  • Advanced Data Structures & Algorithmic Paradigm
  • Fast Range Queries or Amortized Dynamic Operations

Algorithmic Decision Tree:

  • BRUTE_FORCE: Basic prototyping when matrix dimensions or queries are very small.
  • BETTER: When 1D Fenwick trees are already implemented and m is small.
  • OPTIMAL: The standard optimal algorithm for 2D mutable range sum queries.

Connected Patterns:

Segment TreeFenwick TreeDisjoint Set UnionDesign Data Structures

1. Nested Iteration over Submatrix

Intuition

Maintain the matrix as a 2D array. - update(row, col, val): Directly set matrix[row][col] = val in O(1) time. - sumRegion(row1, col1, row2, col2): Use two nested loops iterating from row1 to row2 and col1 to col2, accumulating the sum in O((row2 - row1 + 1) \cdot (col2 - col1 + 1)) = O(m \cdot n) time. For 10,000 operations on a 200 × 200 matrix, this approach takes up to 4 × 108 operations, risking TLE.

When to apply: Basic prototyping when matrix dimensions or queries are very small.

Algorithm

  1. Step 1: Store 2D array matrix.
  2. Step 2: On update(row, col, val), matrix[row][col] = val in O(1).
  3. Step 3: On sumRegion(r1, c1, r2, c2), nested loop r from r1 to r2 and c from c1 to c2 summing matrix[r][c].
  4. Step 4: Return sum.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class NumMatrixBrute {
5 std::vector<std::vector<int>> matrix;
6public:
7 NumMatrixBrute(std::vector<std::vector<int>>& mat) : matrix(mat) {}
8
9 void update(int row, int col, int val) {
10 matrix[row][col] = val;
11 }
12
13 int sumRegion(int row1, int col1, int row2, int col2) {
14 int sum = 0;
15 for (int r = row1; r <= row2; ++r) {
16 for (int c = col1; c <= col2; ++c) {
17 sum += matrix[r][c];
18 }
19 }
20 return sum;
21 }
22};
23
24int main() {
25 std::vector<std::vector<int>> mat = {
26 {3, 0, 1, 4, 2},
27 {5, 6, 3, 2, 1},
28 {1, 2, 0, 1, 5},
29 {4, 1, 0, 1, 7},
30 {1, 0, 3, 0, 5}
31 };
32 NumMatrixBrute nm(mat);
33 std::cout << nm.sumRegion(2, 1, 4, 3) << std::endl;
34 nm.update(3, 2, 2);
35 std::cout << nm.sumRegion(2, 1, 4, 3) << std::endl;
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(1) for update, O(m * n) for sumRegion
  • Space complexity: O(m * n) auxiliary space

2. Row-Wise 1D Binary Indexed Trees

Intuition

Decompose the 2D matrix into m independent 1D Binary Indexed Trees, one per row: - update(row, col, val): Compute \delta = val - matrix[row][col]. Update row's 1D Fenwick tree in O(log n). - sumRegion(row1, col1, row2, col2): Loop across rows r from row1 to row2, querying the 1D Fenwick tree of row r for the range [col1, col2] in O(log n). Overall query takes O((row2 - row1 + 1) log n) <= O(m log n).

When to apply: When 1D Fenwick trees are already implemented and m is small.

Algorithm

  1. Step 1: For each row, construct a 1D BIT of length n + 1.
  2. Step 2: On update(row, col, val), update the BIT of that row with delta in O(log n).
  3. Step 3: On sumRegion, iterate r from row1 to row2, adding range sum of row r from col1 to col2 in O(m log n).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class NumMatrixRowBIT {
5 int m, n;
6 std::vector<std::vector<int>> matrix;
7 std::vector<std::vector<int>> bit;
8
9 void add(int r, int c, int delta) {
10 for (; c <= n; c += c & -c) bit[r][c] += delta;
11 }
12 int query(int r, int c) {
13 int sum = 0;
14 for (; c > 0; c -= c & -c) sum += bit[r][c];
15 return sum;
16 }
17
18public:
19 NumMatrixRowBIT(std::vector<std::vector<int>>& mat) : m(mat.size()), n(mat[0].size()), matrix(mat), bit(mat.size(), std::vector<int>(mat[0].size() + 1, 0)) {
20 for (int r = 0; r < m; ++r) {
21 for (int c = 0; c < n; ++c) {
22 add(r, c + 1, matrix[r][c]);
23 }
24 }
25 }
26
27 void update(int row, int col, int val) {
28 int delta = val - matrix[row][col];
29 matrix[row][col] = val;
30 add(row, col + 1, delta);
31 }
32
33 int sumRegion(int row1, int col1, int row2, int col2) {
34 int sum = 0;
35 for (int r = row1; r <= row2; ++r) {
36 sum += query(r, col2 + 1) - query(r, col1);
37 }
38 return sum;
39 }
40};
41
42int main() {
43 std::vector<std::vector<int>> mat = {
44 {3, 0, 1, 4, 2},
45 {5, 6, 3, 2, 1},
46 {1, 2, 0, 1, 5},
47 {4, 1, 0, 1, 7},
48 {1, 0, 3, 0, 5}
49 };
50 NumMatrixRowBIT nm(mat);
51 std::cout << nm.sumRegion(2, 1, 4, 3) << std::endl;
52 nm.update(3, 2, 2);
53 std::cout << nm.sumRegion(2, 1, 4, 3) << std::endl;
54 return 0;
55}

Time & Space Complexity

  • Time complexity: O(log n) for update, O(m log n) for sumRegion
  • Space complexity: O(m * n) auxiliary space

3. 2D Binary Indexed Tree (2D Fenwick Tree)

Intuition

Generalize the 1D Fenwick Tree into two dimensions: 1. Maintain tree[1...m][1...n]: - Point addition propagates through both row and column indices: for (int r = row; r <= m; r += r & -r) for (int c = col; c <= n; c += c & -c) tree[r][c] += delta; Runs in O(log m \cdot log n). 2. 2D Prefix Query: - Computes sum of submatrix [0, 0] to [r - 1, c - 1]: for (int i = r; i > 0; i -= i & -i) for (int j = c; j > 0; j -= j & -j) sum += tree[i][j]; Runs in O(log m \cdot log n). 3. 2D Range Sum Query via Inclusion-Exclusion: $\text{sumRegion}(r_1, c_1, r_2, c_2) = \text{query}(r_2+1, c_2+1) - \text{query}(r_1, c_2+1) - \text{query}(r_2+1, c_1) + \text{query}(r_1, c_1) 4. Both update and sumRegion run in O(log m \cdot log n) time with O(m \cdot n)$ space.

When to apply: The standard optimal algorithm for 2D mutable range sum queries.

Algorithm

  1. Step 1: Allocate 2D tree of size (m + 1) x (n + 1) and local matrix copy.
  2. Step 2: Initialize 2D BIT by adding initial cell values.
  3. Step 3: On update(row, col, val), calculate delta = val - matrix[row][col], update matrix, propagate delta in 2D BIT.
  4. Step 4: On sumRegion(r1, c1, r2, c2), apply 2D inclusion-exclusion principle with 4 prefix queries in O(log m * log n).

Interactive trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
NumMatrix initialized for 5x5 matrix
Visual state
Values and pointers at this exact step
pointers
S
3
0
1
4
2
0
1
2
3
4
Check / comparison
Tree dimensions (5+1)x(5+1)
Decision / next transition
Ready to query
Why this step matters

NumMatrix initialized for 5x5 matrix. 2D Binary Indexed Tree populated.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class NumMatrix {
5 int m, n;
6 std::vector<std::vector<int>> matrix;
7 std::vector<std::vector<int>> tree;
8
9 void add(int row, int col, int delta) {
10 for (int r = row; r <= m; r += r & -r) {
11 for (int c = col; c <= n; c += c & -c) {
12 tree[r][c] += delta;
13 }
14 }
15 }
16
17 int query(int row, int col) {
18 int sum = 0;
19 for (int r = row; r > 0; r -= r & -r) {
20 for (int c = col; c > 0; c -= c & -c) {
21 sum += tree[r][c];
22 }
23 }
24 return sum;
25 }
26
27public:
28 NumMatrix(std::vector<std::vector<int>>& mat) : m(mat.size()), n(mat[0].size()), matrix(mat), tree(mat.size() + 1, std::vector<int>(mat[0].size() + 1, 0)) {
29 for (int r = 0; r < m; ++r) {
30 for (int c = 0; c < n; ++c) {
31 add(r + 1, c + 1, matrix[r][c]);
32 }
33 }
34 }
35
36 void update(int row, int col, int val) {
37 int delta = val - matrix[row][col];
38 matrix[row][col] = val;
39 add(row + 1, col + 1, delta);
40 }
41
42 int sumRegion(int row1, int col1, int row2, int col2) {
43 return query(row2 + 1, col2 + 1) - query(row1, col2 + 1) - query(row2 + 1, col1) + query(row1, col1);
44 }
45};
46
47int main() {
48 std::vector<std::vector<int>> mat = {
49 {3, 0, 1, 4, 2},
50 {5, 6, 3, 2, 1},
51 {1, 2, 0, 1, 5},
52 {4, 1, 0, 1, 7},
53 {1, 0, 3, 0, 5}
54 };
55 NumMatrix nm(mat);
56 std::cout << nm.sumRegion(2, 1, 4, 3) << std::endl;
57 nm.update(3, 2, 2);
58 std::cout << nm.sumRegion(2, 1, 4, 3) << std::endl;
59 return 0;
60}

Time & Space Complexity

  • Time complexity: O(log m * log n) for both update and sumRegion
  • Space complexity: O(m * n) auxiliary space for the 2D Fenwick tree

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Nested Iteration over SubmatrixO(1) for update, O(m * n) for sumRegionO(m * n) auxiliary spaceStore the 2D matrix directly. update modifies cell in O(1), sumRegion sums the submatrix cells using nested loops in O(m * n).O(1) for update, O(m * n) for sumRegion
2.Row-Wise 1D Binary Indexed TreesO(log n) for update, O(m log n) for sumRegionO(m * n) auxiliary spaceMaintain a 1D Fenwick Tree for each row. update takes O(log n), and sumRegion sums rows in O(m log n).O(log n) for update, O(m log n) for sumRegion
3.2D Binary Indexed Tree (2D Fenwick Tree)OptimalO(log m * log n) for both update and sumRegionO(m * n) auxiliary space for the 2D Fenwick treeMaintain a full 2D Binary Indexed Tree. Updates and prefix queries execute in O(log m * log n) time using 2D bitwise stepping and inclusion-exclusion.O(log m * log n) for both update and sumRegion

Common Pitfalls & Crucial Edge Cases

Signs in inclusion-exclusion formula

Forgetting to ADD the corner query(r1 - 1, c1 - 1) causes undercounting.

1-based indexing offsets in 2D

Forgetting to add 1 to both row and column indices before querying the 2D Fenwick Tree.

Passing new value instead of delta

Fenwick tree point update requires delta = newVal - matrix[r][c].

Crucial Edge Cases to Validate:

  • Single cell query (r1 == r2 and c1 == c2) — Inclusion-exclusion returns exactly that cell's value.
  • Query covers entire matrix (0, 0) to (R - 1, C - 1) — Returns sum of all elements in matrix.
  • Updating a cell multiple times — Delta must be calculated against current cell value.
  • Matrix with 1 row or 1 column — Degenerates gracefully to 1D Fenwick Tree.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Draw the 2D inclusion-exclusion diagram with the 4 intersecting rectangles on the whiteboard.
  2. Point out that a 2D Segment Tree requires 16 * R * C memory, whereas a 2D Fenwick Tree requires only (R + 1) * (C + 1) memory.
  3. Show how clean the nested lowbit update loops are in code.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.How does a 2D Fenwick Tree implement point update and 2D range sum query?

2.How is the 2D range sum of submatrix [r1, c1] to [r2, c2] computed using 2D prefix sums?

3.What is the space complexity of a 2D Fenwick Tree for a matrix of size R x C?

Back to DSA Sheet