308. Range Sum Query 2D - Mutable

Explanation:

In this problem, we are required to design a data structure that supports the following operations efficiently:

NumMatrix(int[][] matrix): Constructor that initializes the data structure with the given matrix.
update(int row, int col, int val): Update the value of the element at matrix[row][col] to be val.
sumRegion(int row1, int col1, int row2, int col2): Return the sum of the elements within the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

To achieve this efficiently, we can use a 2D Binary Indexed Tree (BIT) also known as a Fenwick Tree. This data structure allows us to efficiently calculate prefix sums and update individual elements in a 2D matrix.

Algorithm:

Initialize a 2D Binary Indexed Tree (BIT) with the same dimensions as the input matrix.
In the constructor NumMatrix, we first initialize the BIT with zeros and then update each element in the BIT with the corresponding value from the input matrix.
For update operation, we first calculate the difference between the new value and the previous value at the specified position. Then, we update the BIT at that position with the difference.
For sumRegion operation, we calculate the sum of the rectangle using the prefix sum formula with the BIT.

Time Complexity:

Construction: O(mnlog(m)*log(n)), where m and n are the dimensions of the input matrix.
Update: O(log(m)*log(n))
Query: O(log(m)*log(n))

Space Complexity: O(m*n):

View Leetcode Problem

class NumMatrix {
    int[][] matrix;
    int[][] bit;
    int m, n;

    public NumMatrix(int[][] matrix) {
        m = matrix.length;
        n = matrix[0].length;
        this.matrix = new int[m][n];
        bit = new int[m + 1][n + 1];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                update(i, j, matrix[i][j]);
            }
        }
    }

    public void update(int row, int col, int val) {
        int diff = val - matrix[row][col];
        matrix[row][col] = val;
        
        for (int i = row + 1; i <= m; i += i & -i) {
            for (int j = col + 1; j <= n; j += j & -j) {
                bit[i][j] += diff;
            }
        }
    }

    private int query(int row, int col) {
        int sum = 0;
        for (int i = row + 1; i > 0; i -= i & -i) {
            for (int j = col + 1; j > 0; j -= j & -j) {
                sum += bit[i][j];
            }
        }
        return sum;
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return query(row2, col2) - query(row1 - 1, col2) - query(row2, col1 - 1) + query(row1 - 1, col1 - 1);
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Sign in to devexcode.com with google.com

Explanation:

Code Editor (Testing phase)

Improve Your Solution