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");
}
}
