308. 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 sumRegion and update.

Solution

In my first idea, I tried the straightforward solution, keep them in a matrix, and sum up all the values in the given range. It works ok. It takes about 30 ms run time.

However, it takes square time complexity to get the range sum.

Then, I came out with another solution is to have an extra matrix keep the range square sum result form [0,0] to [i,j]. It can optimally reduce the time of computing the range sum. However, it also makes the update operation less effient. So the time is increasing to 40ms.

Then the final one is the best so far. I just keep the row accumulated result. It share the loading to update and rangeSum. It took only 11 ms.

class NumMatrix {
    int[][] mat;
    int[][] sum;
    int m = 0;
    int n = 0;
    public NumMatrix(int[][] matrix) {
        mat = matrix;
        m = matrix.length;
        n = matrix[0].length;
        sum = new int[m][n];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                sum[i][j] = matrix[i][j] + (j > 0 ? sum[i][j-1] : 0);
            }
        }
        
    }
    
    public void update(int row, int col, int val) {
        
        for(int j = col; j < n; j++){
            sum[row][j] = sum[row][j] - mat[row][col] + val;
        }
        mat[row][col] = val;
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int ret = 0;
        
        for(int i = row1; i <= row2; i++){
            ret += sum[i][col2] - (col1 > 0 ? sum[i][col1-1] : 0);
        }
        return ret;
    }
}