308. 2D area and retrieval - variable segment tree / hash

308. Two dimensional region and retrieval  

Here's a two-dimensional matrix for you  matrix , You need to handle several queries of the following two types ：

1. to update ： to update  matrix  The value of a cell in .
2. Sum up ： Calculation of matrix  matrix  Of a rectangular area element in   and  , This area is controlled by   top left corner  (row1, col1)  and   The lower right corner  (row2, col2)  Definition .

Realization  NumMatrix  class ：

• NumMatrix(int[][] matrix)  Using integer matrix  matrix  Initialize object .
• void update(int row, int col, int val)  to update  matrix[row][col]  Value to  val .
• int sumRegion(int row1, int col1, int row2, int col2)  Return matrix  matrix  Of the rectangular area element specified in   and  , This area is controlled by   top left corner  (row1, col1)  and   The lower right corner  (row2, col2)  Definition .

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]

 explain 
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 ( namely ,  The sum of the red rectangle on the left )
numMatrix.update(3, 2, 2);       //  The matrix changes from left to right 
numMatrix.sumRegion(2, 1, 4, 3); //  return  10 ( namely , And of the red rectangle on the right )

Tips ：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 200
• -105 <= matrix[i][j] <= 10^5
• 0 <= row < m
• 0 <= col < n
• -105 <= val <= 10^5
• 0 <= row1 <= row2 < m
• 0 <= col1 <= col2 < n
• Call at most 10^4  Time  sumRegion  and  update  Method

 

The result of doing the question

success , Two solutions are used

Method 1： Hash

Lazy loaded two-dimensional prefix and , The good thing is always update Or always sum , Complexity is still O(1), Alternate is O(mn)

1. Initialize prefix and

2. When updating data , Mark

3.  When getting marked , Update the array , Remove the mark

class NumMatrix {
        int[][] arr;
        int[][] pre;
        int m;
        int n;
        boolean hasChange;
        public NumMatrix(int[][] matrix) {
            arr = matrix;// Change prefix and ...
            m = matrix.length;
            n = matrix[0].length;
            pre = new int[m+1][n+1];
            for(int i = 0; i<m; i++){
                for(int j = 0; j < n; j++){
                    pre[i+1][j+1]=matrix[i][j]+pre[i][j+1]+pre[i+1][j]-pre[i][j];
                }
            }
        }

        public void update(int row, int col, int val) {
            arr[row][col] = val;
            hasChange = true;
        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            if(hasChange){
                for(int i = 0; i<m; i++){
                    for(int j = 0; j < n; j++){
                         pre[i+1][j+1]=arr[i][j]+pre[i][j+1]+pre[i+1][j]-pre[i][j];
                    }
                }
                hasChange = false;
            }

            return pre[row2+1][col2+1]+pre[row1][col1]-pre[row1][col2+1]-pre[row2+1][col1];
        }
    }

Method 2： Line segment tree  

This problem is actually a two-dimensional line segment tree , Record the upper left and lower right corners , There are four points

1. Create a line tree , There are four points , One and , Two children

2. When recursively assigning children , Preferred Branch , Reclassification 【 convenient , Four at a time is OK , There will be more to judge 】

3. Calculate the child's value , Push up one by one , Get the whole prefix and

4. Additive elements ： Returns... Out of range , Recursively add... Within the scope , Pass it on to the child

5. Sum up ： Current range value , All return directly within the target range sum; Do not return directly within the target 0; Otherwise, the child's sum will be accumulated

class NumMatrix {
        SquareTree tree;
        int[][] arr;
        public NumMatrix(int[][] matrix) {
            arr = matrix;
            tree = new SquareTree(0,0,matrix.length-1,matrix[0].length-1,matrix);
        }

        public void update(int row, int col, int val) {
            int diff = val-arr[row][col];
            arr[row][col] = val;
            tree.add(row,col,diff);
        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            return tree.getSum(row1,col1,row2,col2);
        }
    }

class SquareTree{
    int x1;
    int x2;
    int y1;
    int y2;
    int sum;
    SquareTree t1;
    SquareTree t2;
    public SquareTree(int x1, int y1, int x2, int y2,int[][] arr){
        this.x1 = x1;
        this.y1 = y1;
        this.x2 = x2;
        this.y2 = y2;
        sum = initSum(x1,y1,x2,y2,arr);
    }

    private int initSum(int X1, int Y1, int X2, int Y2, int[][] arr){
        if(X1==X2 && Y1 == Y2){
            sum = arr[X1][Y1];
            return sum;
        }
        if(x1<x2){
            int mid = (x2-x1)/2+x1;
            t1 = new SquareTree(x1,y1,mid,y2,arr);
            t2 = new SquareTree(mid+1,y1,x2,y2,arr);
        }else{
            int mid = (y2-y1)/2+y1;
            t1 = new SquareTree(x1,y1,x2,mid,arr);
            t2 = new SquareTree(x1,mid+1,x2,y2,arr);
        }

        sum = t1.sum+t2.sum;
        return sum;
    }

    public void add(int x, int y,int v){
        if(x<x1||x>x2||y<y1||y>y2){
            return;
        }
        sum += v;
        if(t1!=null)
            t1.add(x,y,v);
        if(t2!=null)
            t2.add(x,y,v);
    }



    public int getSum(int X1, int Y1, int X2, int Y2){
        if(x2<X1||x1>X2||y2<Y1||y1>Y2){
            return 0;
        }
        // All within the scope 
        if(X1<=x1&&X2>=x2&&Y1<=y1&&Y2>=y2){
            return sum;
        }

        return t1.getSum(X1,Y1,X2,Y2)+t2.getSum(X1,Y1,X2,Y2);
    }

}