AlgoMaster Logo

Range Sum Query 2D - Mutable

hardFrequencyUpdated September 21, 2026

Understanding the Problem

This is the mutable version of Range Sum Query 2D - Immutable (LeetCode 304). When the matrix never changes, a 2D prefix sum gives O(1) queries after O(m * n) preprocessing.

Here the matrix can change. A call to update(row, col, val) makes the precomputed 2D prefix sum stale, because a single cell affects every prefix-sum entry below and to the right of it. Rebuilding the entire table after each update costs O(m n). With up to 5000 operations on a 200x200 matrix, that is up to 5000 40000 = 200 million additions for updates alone.

The question is what data structure handles both a cell update and a rectangle-sum query efficiently, instead of recomputing everything from scratch on each operation or precomputing everything upfront and paying for every update.

Key Constraints:

  • 1 <= m, n <= 200 -> The matrix is at most 200x200 = 40,000 cells. An O(m * n) cost per operation is 40,000 work units, which over 5000 operations reaches 200 million. That rules out rebuilding a full prefix table on every update.
  • At most 5000 calls to update and sumRegion -> The workload mixes updates and queries, so both operations have to be fast, not just one.
  • -10^5 <= val <= 10^5 -> Values can be negative, so no approach can assume positivity. The sumRegion return type is a 32-bit int, so the problem guarantees every region sum fits in 32 bits. A 32-bit accumulator is therefore safe.

Approach 1: Brute Force (Recompute on Query)

Intuition

Store the matrix as-is, write updates directly into it, and answer each sum query by iterating over every cell in the rectangle and adding them.

There is no preprocessing. An update is a single array write, so it costs O(1). A query traverses the whole sub-rectangle every time, so its cost scales with the rectangle's area.

Algorithm

  1. Store the matrix directly.
  2. On update(row, col, val), set matrix[row][col] = val.
  3. On sumRegion(row1, col1, row2, col2), iterate through every row from row1 to row2 and every column from col1 to col2, accumulating the sum.
  4. Return the accumulated sum.

Example Walkthrough

Input:

0
1
2
3
4
0
3
0
1
4
2
1
5
6
3
2
1
2
1
2
0
1
5
3
4
1
0
1
7
4
1
0
3
0
5
matrix

For sumRegion(2, 1, 4, 3), iterate over every cell in rows 2 through 4, columns 1 through 3, and sum them:

  • Row 2, columns 1-3: matrix[2][1..3] = 2 + 0 + 1 = 3
  • Row 3, columns 1-3: matrix[3][1..3] = 1 + 0 + 1 = 2
  • Row 4, columns 1-3: matrix[4][1..3] = 0 + 3 + 0 = 3
  • Total: 3 + 2 + 3 = 8

For update(3, 2, 2), set matrix[3][2] = 2. The cell at row 3, column 2 changes from 0 to 2. Nothing else is touched.

For sumRegion(2, 1, 4, 3) again, the same scan now sees the updated cell in row 3:

  • Row 2, columns 1-3: 2 + 0 + 1 = 3
  • Row 3, columns 1-3: 1 + 2 + 1 = 4 (the middle cell is now 2)
  • Row 4, columns 1-3: 0 + 3 + 0 = 3
  • Total: 3 + 4 + 3 = 10

Code

Each sumRegion call recomputes the same sums from scratch over the whole rectangle. The next approach precomputes partial sums along one dimension so a query reads each row's contribution in constant time.

Approach 2: Row Prefix Sums

Intuition

Precompute a prefix sum for each row independently. A full 2D prefix sum is too expensive to maintain because one cell change invalidates the entire table. Per-row prefix sums localize the damage: a cell at matrix[row][col] affects only row row's prefix sums, so an update rebuilds a single row in O(n).

A query iterates over each row in the range and reads that row's contribution in O(1) from its prefix sum, so the query costs O(m), the number of rows in the rectangle.

Define rowPrefix[r][c] as the sum of matrix[r][0..c-1]. The sum of columns col1 through col2 in row r is then rowPrefix[r][col2 + 1] - rowPrefix[r][col1]. Loop over rows row1 to row2 and accumulate these differences.

Algorithm

  1. Build a prefix sum array for each row: rowPrefix[r][c] = matrix[r][0] + matrix[r][1] + ... + matrix[r][c-1].
  2. On update(row, col, val), update matrix[row][col] = val, then rebuild the prefix sum for row row in O(n).
  3. On sumRegion(row1, col1, row2, col2), for each row r from row1 to row2, add rowPrefix[r][col2 + 1] - rowPrefix[r][col1] to the total.
  4. Return the total.

Example Walkthrough

1Initial matrix. Query: sumRegion(2, 1, 4, 3). Highlight target rectangle.
0
1
2
3
4
0
3
0
1
4
2
1
5
6
3
2
1
2
1
2
0
1
5
3
4
1
0
1
7
4
1
0
3
0
5
1/8

Code

The query still scales linearly with the number of rows in the rectangle, and the update scales linearly with the number of columns. A Binary Indexed Tree brings both point updates and prefix-sum queries down to logarithmic time, and it extends to two dimensions.

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

Intuition

A Binary Indexed Tree (BIT), also called a Fenwick Tree, supports point updates and prefix sum queries in O(log n) each in one dimension, and the same structure extends to two dimensions.

Maintain a 2D array tree of size (m+1) x (n+1) where each position holds a partial sum over a range of cells. To update matrix[row][col], compute the delta and propagate it through the tree using i += i & (-i) in both dimensions. To read a prefix sum, traverse in the reverse direction using i -= i & (-i), accumulating values. The expression i & (-i) isolates the lowest set bit of i, which is the width of the range that index is responsible for.

To get the sum of an arbitrary rectangle, combine four prefix sum queries by inclusion-exclusion:

sumRegion(r1, c1, r2, c2) = prefix(r2, c2) - prefix(r1-1, c2) - prefix(r2, c1-1) + prefix(r1-1, c1-1)

Here prefix(r, c) is the sum of all cells from (0,0) to (r,c). Subtracting the strip above the rectangle and the strip to its left removes the top-left corner block twice, so the final term adds it back once. When r1 or c1 is 0, the corresponding prefix(-1, ...) term is 0, which the BIT traversal produces because the loop index i = row + 1 becomes 0 and the loop never runs.

Algorithm

  1. Create a 2D BIT array tree of size (m+1) x (n+1), initialized to zero. Also keep a copy of the matrix for computing deltas on update.
  2. Build the tree by calling the BIT update for each cell in the original matrix.
  3. On update(row, col, val), compute delta = val - matrix[row][col], update matrix[row][col] = val, then propagate delta through the BIT.
  4. On sumRegion(row1, col1, row2, col2), compute four prefix sums and combine with inclusion-exclusion.

Example Walkthrough

Take the matrix [[1,2,3],[4,5,6],[7,8,9]] and the query sumRegion(1, 1, 2, 2), which sums the bottom-right 2x2 block: 5 + 6 + 8 + 9 = 28. The four prefix sums are prefix(2,2) = 45 (the whole matrix), prefix(0,2) = 6 (top row), prefix(2,0) = 12 (left column), and prefix(0,0) = 1. Inclusion-exclusion gives 45 - 6 - 12 + 1 = 28.

After update(1, 1, 10), the center cell changes from 5 to 10, a delta of +5. The BIT propagates that delta to the nodes covering (1,1). Re-running the query, prefix(2,2) rises to 50 while the other three terms stay the same (they do not cover the changed cell), so the new sum is 50 - 6 - 12 + 1 = 33, exactly 5 more than before.

1Built 2D BIT from matrix. Query: sumRegion(1,1,2,2)
0
1
2
0
1
2
3
1
4
5
6
2
7
8
9
1/8

Code