LeetCode Top 100 Liked Questions 308. Range Sum Query 2D - Mutable (Java版; Hard)

爱被打了一巴掌 2023-07-04 03:26 22阅读 0赞

### [welcome to my blog][] ###

## LeetCode Top 100 Liked Questions 308. Range Sum Query 2D - Mutable (Java版; Hard) ##

#### 题目描述 ####

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left 
    corner (row1, col1) and lower right corner (row2, col2).

![format_png][]

The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3),
    which contains sum = 8.
    
    Example:
    Given 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]
    ]
    
    sumRegion(2, 1, 4, 3) -> 8
    update(3, 2, 2)
    sumRegion(2, 1, 4, 3) -> 10
    Note:
    The matrix is only modifiable by the update function.
    You may assume the number of calls to update and sumRegion function is distributed evenly.
    You may assume that row1 ≤ row2 and col1 ≤ col2.

#### 第一次做; 没有使用线段树或者树状数组, 而是多次使用了一维前缀和 ####

class NumMatrix { 
        
        private int[][] matrix;
        private int[][] sum;
        
        public NumMatrix(int[][] matrix) { 
            this.matrix = matrix;
            getSumArr(matrix);
        }
        
        public void update(int row, int col, int val) { 
            int diff = val - matrix[row][col];
            //记得更新matrix[row][col], 要不多次修改同一个位置后, 还是用最原始的matrix计算diff的值, 这样就错了!
            matrix[row][col] = val;
            //细节: j的起始值, 要时刻牢记sum[i][j]的含义
            for(int j=col+1; j<sum[0].length; j++){ 
                sum[row][j] = sum[row][j] + diff;
            }
        }
        
        public int sumRegion(int row1, int col1, int row2, int col2) { 
            int res = 0;
            for(int i=row1; i<=row2; i++){ 
                res = res + sum[i][col2+1] - sum[i][col1];
            }
            return res;
        }
        
        private void getSumArr(int[][] matrix){ 
            //input check
            if(matrix==null || matrix.length==0 || matrix[0]==null || matrix[0].length==0)
                return;
            int rows = matrix.length, cols = matrix[0].length;
            /* sum[i][j]表示matrix索引为i那一行的前j个数的和 sum[i][j]=matrix[i][0]+matrix[i][1]+...+matrix[i][j-1] sum[i][j]=sum[i][j-1] + matrix[i][j-1] */
            sum = new int[rows][cols+1];
            for(int i=0; i<rows; i++){ 
                for(int j=1; j<=cols; j++){ 
                    sum[i][j] = sum[i][j-1] + matrix[i][j-1];
                }
            }
        }
    }
    
    /** * Your NumMatrix object will be instantiated and called as such: * NumMatrix obj = new NumMatrix(matrix); * obj.update(row,col,val); * int param_2 = obj.sumRegion(row1,col1,row2,col2); */

#### 力扣优秀题解(https://leetcode-cn.com/problems/range-sum-query-2d-mutable/solution/wu-xu-xian-duan-shu-de-gao-xiao-jie-fa-20ms-ji-bai/) ####

新建一个数组rowSumArr来存放各个位置(i, j) 的前j+1项的和，即从(i, 0) 到 (i, j)各个元素的和。
    若更新（执行update方法）的时候，只需要更新要被更新位置(i, j)所在行的后面的元素的rowSumArr的值即可。
    若要计算二维区域和（执行sumRegion方法）的时候，只要求得二维区域每一行的元素之和，之后累加即可。
    这里刚好可以利用到前面保存的rowSumArr上的值，每一行的和只要O(1)的时间复杂度即可，整体只要O(n)时间复杂度。

class NumMatrix { 
    
            private int[][] matrix;
            private int[][] rowSumArr;  // 保存每个元素(i, j)在第i行的前j+1项的和。
            private int rowCount;
            private int colCount;
    
            public NumMatrix(int[][] matrix) { 
                this.matrix = matrix;
                if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { 
                    return;
                }
    
                rowCount = matrix.length;
                colCount = matrix[0].length;
                rowSumArr = new int[rowCount][colCount];
                for (int i = 0; i < rowCount; i++) { 
                    rowSumArr[i][0] = matrix[i][0];
                    for (int j = 1; j < colCount; j++) { 
                        rowSumArr[i][j] = rowSumArr[i][j-1] + matrix[i][j];
                    }
                }
            }
    
            public void update(int row, int col, int val) { 
                matrix[row][col] = val;
                int fromCol = col;
                if (col == 0) { 
                    rowSumArr[row][col] = matrix[row][col];
                    fromCol = col + 1;
                }
                for (int j = fromCol; j < colCount; j++) { 
                    rowSumArr[row][j] = rowSumArr[row][j-1] + matrix[row][j];
                }
            }
    
            public int sumRegion(int row1, int col1, int row2, int col2) { 
                int sum = 0;
                for (int i = row1; i <= row2; i++) { 
                    sum += col1 == 0 ? rowSumArr[i][col2] : rowSumArr[i][col2] - rowSumArr[i][col1-1];
                }
                return sum;
            }
        }

##### [树状数组的优秀讲解][Link 1] #####

[welcome to my blog]: https://littlehaes.com
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS9mNzhjMjY5Njc3Njg4MTkxMDMwYTdhNTA1MTEzMjI0Mi94bWxub3RlLzYyNkI1OTExODY4RjRERTQ5MDc3QjczQUJBMDBFNENFLzU4NTAx?x-oss-process=image/format,png
[Link 1]: https://blog.csdn.net/Yaokai_AssultMaster/article/details/79492190#t5