27 IndexTree

IndexTree特点：
1）支持区间查询
2）没有线段树那么强，但是非常容易改成一维、二维、三维的结构
3）只支持单点更新

IndexTree实现

对于前缀和数组，当原数组不变时，可以快速获取某个范围累加和，但是当原数组一个范围的数发生改变时，前缀和数组受影响，需要重新计算，时间复杂度高。

IndexTree 下标从1开始
tree[1]管理原数组下标1；tree[2]管理原数组下标1、2；tree[3]管理原数组3；tree[4]管理原数组1、2、3、4

每个下标负责：该下标的二进制 左右边的1去掉+1~该下边范围的数
如下标4，对应二进制 0100 ——》最右边1去掉+1 = 0001~0100范围的数

public static class IndexTree {
    private final int[] tree;
    private final int num;
    public IndexTree(int size) {
        num = size;
        tree = new int[num + 1];
    }
    // 当前位置 加上 去掉最右边1的位置 
    public int sum(int index) {
        int res = 0;
        while (index > 0) {
            res += tree[index];
            index -= index & -index;
        }
        return res;
    }
    // 受影响的位置 当前位置，和 加上最右边的1 的位置
    public void add(int index, int d) {
        while (index <= num) {
            tree[index] += d;
            index += index & -index;
        }
    }
}
public static class Right {
    private final int[] nums;
    public Right(int size) {
        int n = size + 1;
        nums = new int[n + 1];
    }
    public int sum(int index) {
        int ret = 0;
        for (int i = 1; i <= index; i++) {
            ret += nums[i];
        }
        return ret;
    }
    public void add(int index, int d) {
        nums[index] += d;
    }
}

IndexTree可方便用于二维数组

每一维做 运算

public static class IndexTree2D {
    private int[][] tree;
    private int[][] nums;
    private int r;
    private int c;

    public IndexTree2D(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        r = matrix.length;
        c = matrix[0].length;
        tree = new int[r + 1][c + 1];
        nums = new int[r][c];
        for (int i = 0; i < matrix.length; i++) {
            System.arraycopy(matrix[i], 0, nums[i], 0, c);
            System.arraycopy(matrix[i], 0, tree[i + 1], 1, c);
        }
    }

    public int sum(int row, int col) {
        int res = 0;
        for (int i = row + 1; i > 0; i -= (i & -i)) {
            for (int j = col + 1; j > 0; j -= (j & -j)) {
                res += tree[i][j];
            }
        }
        return res;
    }

    public void update(int row, int col, int d) {
        if (r == 0 || c == 0) {
            return;
        }

        int add = d - nums[row][col];
        nums[row][col] = d;
        for (int i = row + 1; i <= r; i += (i & -i)) {
            for (int j = col + 1; j <= c; j += (j & -j)) {
                tree[i][j] += add;
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        if (r == 0 || c == 0) {
            return 0;
        }
        return sum(row2, col2) + sum(row1 - 1, col1 - 1) - sum(row1 - 1, col2) - sum(row2, col1 - 1);
    }
}