308. 二维区域和检索 - 可变

文章目录

• 308. 二维区域和检索 - 可变
• 一、解题思路
• 二、代码

---

308. 二维区域和检索 - 可变

给你一个二维矩阵 matrix ，你需要处理下面两种类型的若干次查询：

更新：更新 matrix 中某个单元的值。
求和：计算矩阵 matrix 中某一矩形区域元素的 和 ，该区域由 左上角 (row1, col1) 和 右下角 (row2, col2) 界定。
实现 NumMatrix 类：

NumMatrix(int[][] matrix) 用整数矩阵 matrix 初始化对象。
void update(int row, int col, int val) 更新 matrix[row][col] 的值到 val 。
int sumRegion(int row1, int col1, int row2, int col2) 返回矩阵 matrix 中指定矩形区域元素的 和 ，该区域由 左上角 (row1, col1) 和 右下角 (row2, col2) 界定。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/range-sum-query-2d-mutable

一、解题思路

使用线段树,Tree数组记录(0,0)到(i,j)的累加和,nums记录matrix的值
从一维到二维我们需要分析如果某个位置发生变化,将会影响Tree数组哪些位置
在一维中,如果原数组matrix[i] (假设i为4,数组长度为12) 发生变化,那么Tree[00100(4)],Tree[01000(8)]需要发生变化
推广到二维,我们把需要发生变化的行和列进行组合,即为全部要发生变化的位置

二、代码

class NumMatrix {
    int[][] Tree;
    int[][] nums;
    int N;
    int M;
    public NumMatrix(int[][] matrix) {
        if(matrix.length==0||matrix[0].length==0){
            return;
        }
        N=matrix.length;
        M=matrix[0].length;
        Tree=new int[N+1][M+1];
        nums=new int[N][M];
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                update(i,j,matrix[i][j]);
            }
        }
    }
    
    public int sum(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+=Tree[i][j];
            }
        }
        return sum;
    }

    public void update(int row, int col, int val) {
        if (N == 0 || M == 0) {
			return;
		}
        int add=val-nums[row][col];
        nums[row][col]=val;
        for(int i=row+1;i<=N;i+=i&(-i)){
            for(int j=col+1;j<=M;j+=j&(-j)){
                Tree[i][j]+=add;
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        if (N == 0 || M == 0) {
			return 0;
		}
        return sum(row2,col2)+sum(row1-1,col1-1)-sum(row1-1,col2)-sum(row2,col1-1);
    }
}