IndexTree

IndexTree解决的问题

线段树支持区间更新，但是IndexTree只支持单点更新。

假设给定一个数组，如果频繁的要求某个范围的累加和，在原数组不变的情况下，可以申请一个辅助数组做前缀和（help），然后只需要在辅助数组查询两次就可以得到某个范围上的累加和了！

但是，如果原数组某个变动了的话，前缀和就无法实现了。

所以要用到IndexTree，下图表示help数组每个位置记录原数组哪些范围，比如：1位置记录的是原数组1到1位置上的累加和、2位置记录的是原数组1到2位置上的累加和...

（help数组不是上面提到的前缀和数组！！！）

两个规律

第一个：假设某一个index的二进制表示形式如下，index为help数组中的下标i，那么index位置的值表示记录原数组哪些范围的值呢？010110001 ~ 010111000

举例


第二个：如果想求原数组中从 1 ~ i 位置的前缀和，假设 i 为33，如何利用help数组求？

i 转换为二进制形式，33位置上只管自己，但是32位置上管的是从1到32位置上的所有，所以它两一累加就实现了1到33的累加

假设要求原数组中从1到index位置的累加和（index等于52，index的二进制是 0110100），如何利用help数组求？

help[0110100] + help[0110000] + help[0100000]

那么help数组中index位置上管的是原数组中哪些范围的值呢？

help[0110100] = help[0110001] ~ help[0110100]
help[0110000] = help[0100001] ~ help[0110000]
help[0100000] = help[0000001] ~ help[0100000]

仔细看上面红色加粗字体（从下往上看），是不是就是连起来了呢，所以原数组中从1到index位置的累加和就这样利用help数组求出来了

add方法

假设原数组中3位置的值发生了变化，那么如何知道help数组中哪些位置的值也发生了变化呢？

将3化为二进制形式后，提取出最右侧的1再加上自己，

011 -> 100 -> 1000 -> 10000...，那么在help数组中，这些位置的数都随之发生改动。

时间复杂度

O(logN)，因为是在位信息上操作，有几个位信息就做几次操作，位数就是logN次

总结

一维IndexTree很容易的实现了单点更新和 1 ~ index位置上的前缀和，

如何实现任意一个范围 L到R的前缀和呢？

稍微一加工就可以了：1到R 减去 1到L-1 就实现了

问题是这些功能线段树也可以实现，并且时间复杂度都一样，那么IndexTree存在的意义是什么呢？

线段树是一维的，推成二维很麻烦，而IndexTree推成二维很容易！！！

代码实现

package com.harrison.class22;

/**
 * @author Harrison
 * @create 2022-04-02-9:39
 * @motto 众里寻他千百度，蓦然回首，那人却在灯火阑珊处。
 */
public class Code01_IndexTree {
    // 下标从1开始
    public static class IndexTree{
        private int[] tree;
        private int N;

        // 0位置弃而不用
        public IndexTree(int size){
            N=size;
            tree=new int[N+1];
        }

        // 1~index累加和是多少
        /*
        补充一个小知识：负数的二进制用其正数的补码形式表示
        补码：反码+1
         */
        public int sum(int index){
            int ret=0;
            while(index>0){
                ret+=tree[index];
                index-=index&(-index);// index-=(index & (~index+1))
            }
            return ret;
        }

        // index & -index : 提取出index最右侧的1出来
        // index :           0011001000
        // index & -index :  0000001000
        public void add(int index,int d){
            while(index<=N){
                tree[index]+=d;
                index+=index&(-index);
            }
        }
    }

    public static class Right{
        private int[] nums;
        private int N;

        public Right(int size){
            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;
        }
    }

    public static void main(String[] args) {
        int N = 100;
        int V = 100;
        int testTime = 2000000;
        IndexTree tree = new IndexTree(N);
        Right test = new Right(N);
        System.out.println("test begin");
        for (int i = 0; i < testTime; i++) {
            int index = (int) (Math.random() * N) + 1;
            if (Math.random() <= 0.5) {
                int add = (int) (Math.random() * V);
                tree.add(index, add);
                test.add(index, add);
            } else {
                if (tree.sum(index) != test.sum(index)) {
                    System.out.println("Oops!");
                }
            }
        }
        System.out.println("test finish");
    }
}