LeetCode 308: Range Sum Query 2D - Mutable Solution

Master LeetCode problem 308 (Range Sum Query 2D - Mutable), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

308. Range Sum Query 2D - Mutable

Medium

Array Design Binary Indexed Tree Segment Tree Matrix

Problem Explanation

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):

Solution Code

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);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 308 (Range Sum Query 2D - Mutable)?

This page provides optimized solutions for LeetCode problem 308 (Range Sum Query 2D - Mutable) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 308 (Range Sum Query 2D - Mutable)?

The time complexity for LeetCode 308 (Range Sum Query 2D - Mutable) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 308 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 308 in Java, C++, or Python.

Back to LeetCode Solutions