Range Sum Query 2D — Mutable

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
• -105 <= matrix[i][j] <= 105
• 0 <= row < m
• 0 <= col < n
• -105 <= val <= 105
• 0 <= row1 <= row2 < m
• 0 <= col1 <= col2 < n
• At most 104 calls will be made to update and sumRegion.

Approach: 2D Fenwick Tree (Binary Indexed Tree)

Algorithm

1. Maintain a Fenwick tree over the matrix where each cell accumulates the sums of the submatrix that it is responsible for
2. In the constructor, seed the tree by adding every matrix[i][j] at position (i+1, j+1)
3. For update, compute the difference diff = val - matrix[row][col], update the stored matrix, and add diff to the tree starting from (row+1, col+1)
4. A prefix(row, col) helper returns the sum of the submatrix [0..row-1] x [0..col-1] by walking down the row and column low-bits
5. sumRegion combines four prefix queries using inclusion-exclusion: prefix(r2+1, c2+1) - prefix(r1, c2+1) - prefix(r2+1, c1) + prefix(r1, c1)

Time & Space Complexity

• Time Complexity: O(log m log n) per update and sumRegion; O(mn log m log n) for the build
• Space Complexity: O(mn) - the (m+1) x (n+1) Fenwick tree plus the stored matrix

Java Implementation

public class NumMatrix {

    private final long[][] tree;
    private final int[][] matrix;
    private final int m;
    private final int n;

    public NumMatrix(int[][] matrix) {
        this.matrix = matrix;
        this.m = matrix.length;
        this.n = matrix[0].length;
        this.tree = new long[m + 1][n + 1];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                add(i + 1, j + 1, matrix[i][j]);
            }
        }
    }

    public void update(int row, int col, int val) {
        long diff = val - matrix[row][col];
        matrix[row][col] = val;
        add(row + 1, col + 1, diff);
    }

    private void add(int r, int c, long delta) {
        for (int i = r; i <= m; i += i & -i) {
            for (int j = c; j <= n; j += j & -j) {
                tree[i][j] += delta;
            }
        }
    }

    private long prefix(int r, int c) {
        long sum = 0;
        for (int i = r; i > 0; i -= i & -i) {
            for (int j = c; j > 0; j -= j & -j) {
                sum += tree[i][j];
            }
        }
        return sum;
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        long sum = prefix(row2 + 1, col2 + 1)
                - prefix(row1, col2 + 1)
                - prefix(row2 + 1, col1)
                + prefix(row1, col1);
        return (int) sum;
    }

    // Test method
    public static void main(String[] args) {
        int[][] matrix = {
                {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 numMatrix = new NumMatrix(matrix);
        System.out.println("sumRegion(2, 1, 4, 3): " + numMatrix.sumRegion(2, 1, 4, 3)); // Expected: 8
        numMatrix.update(3, 2, 2);
        System.out.println("sumRegion(2, 1, 4, 3): " + numMatrix.sumRegion(2, 1, 4, 3)); // Expected: 10
    }
}

Example Walkthrough

For matrix = [[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]]:

1. The constructor adds all 25 cells into the 2D Fenwick tree
2. sumRegion(2, 1, 4, 3) = prefix(5, 4) - prefix(2, 4) - prefix(5, 1) + prefix(2, 1) = 8
3. update(3, 2, 2) adds diff = 2 - 0 = 2 to the tree at (4, 3)
4. sumRegion(2, 1, 4, 3) now includes that extra 2 and returns 10

Key Points

1. 2D Fenwick Tree: Extends the 1D BIT by nesting two low-bit loops over rows and columns
2. Inclusion-Exclusion: A rectangle sum is the sum of four prefix queries
3. Point Update: Only O(log m log n) responsible cells are touched per update
4. Difference Trick: update stores only val - oldValue, so the stored matrix stays in sync with the tree
5. Long Accumulation: With values up to 10^5 in a 200 x 200 matrix, sums can exceed int, so the tree uses long