IndexTree2D

A two-dimensional IndexTree Problem solved

A one-dimensional IndexTree The problem to deal with is in a one-dimensional array , A two-dimensional IndexTree The problem to deal with is in a two-dimensional array .help [ i ] [ j ] Indicates that the original array is made in the upper left corner from the first row and the first column ,i,j Make the lower right corner , The accumulation and filling of this whole area is help [ i ] [ j ] In this grid .

without doubt , It is much more complicated than one-dimensional structure , If the value of a certain position of the original array changes , that help The positions affected by the array may be quite many .

for instance , The row number in the original array is 0110100, The column number is 0111000, The value of this position has changed , that help Which corresponding values in the array will change ？

It's easy to push from one dimension to two dimensions , stay help Array , Line number from 0110001 ~ 0110100、 Column number from 0110001 ~ 0111000, This whole combination area is all affected .

Again , 3D can also be pushed like this , This is IndexTree The advantages of , The line segment tree can also be changed into two-dimensional 、 The three dimensional , But it's troublesome

What if you want to find the cumulative sum of any region in a two-dimensional array ？（help Array support is from [ 1,1 ] To [ i , j ] The cumulative sum of positions ）

such as , Want to ask for [ 3,3 ] To [ 4, 4 ] The cumulative sum of the whole , It can be calculated in blocks

The cumulative sum of any piece , Can be in help Take four values from the array and process them

Time complexity

LeetCode 308. Two dimensional region and retrieval - variable （ The prefix and ）

Code

package com.harrison.class22;

/** * @author Harrison * @create 2022-04-02-9:58 * @motto  looking for him for thousand times in the crowd , Suddenly look back , The man was in the dim light . */

//  Test link ：https://leetcode.com/problems/range-sum-query-2d-mutable
//  But this question is a paid question 
//  Submit the class name 、 Constructor name from Code02_IndexTree2D Change to NumMatrix
public class Code02_IndexTree2D {
    
    private int[][] tree;
    private int[][] nums;
    private int N;
    private int M;

    public Code02_IndexTree2D(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]);
            }
        }
    }

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

    // [row,col] The value of the location is updated to val  Equivalent to adding one  add（ Subtract the old value from the current value ）
    public void update(int row, int col, int val) {
    
        if (N == 0 || M == 0) {
    
            return;
        }
        //  The added value  ==  Subtract the old value from the current value 
        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);
    }
}