IndexTree（树状数组）

线段树解决的是 区间查询 和 区间更新 的问题&＃xff0c; $O(logn)$ 复杂度。

人为规定&＃xff1a;数组下标从 1 开始。

如果要计算数组某个范围 L 到 R 的累加和&＃xff0c;那么可以准备一个前缀和数组 help&＃xff0c;得到前缀和数组后&＃xff0c;可以$O(1)$ 复杂度 快速求出 L 到 R 的累加和。

如原数组 arr &＃61; [5, 3, 2, 4, 9, 0, 1]&＃xff0c;则 help &＃61; [5, 8, 10, 14, 23, 23, 24]&＃xff0c;如果要计算下标 3 ~ 5 的值的累加和&＃xff0c;直接用 help[5] - help[2] &＃61; 15&＃xff0c;求解速度非常快。但是这种求解数组某个范围的累加和的方法是基于原数组 arr 不再变化的前提。

如果原数组中的某个数修改了值&＃xff0c;那么 help 数组就存在需要大量更新的问题。

那么对于原数组中的值可能变化的情况&＃xff0c;但是还能查询范围上的累加和&＃xff0c;需要换个结构。即该结构同时满足以下两个方法&＃xff1a;
1&＃xff09;update(i, v)&＃xff1a;将 i 位置的值修改为 v&＃xff1b;
2&＃xff09;sum[L...R]&＃xff1a;计算 L 到 R 范围的累加和。

这个结构就是 Index Tree&＃xff0c;上述的两个方法线段树可以完美实现&＃xff0c;但是 Index Tree 有比线段树更优的地方。

Index Tree 没法像线段树一样做到范围更新&＃xff0c;只能单点更新后执行范围累加和的查询&＃xff0c;这两个方法都快。

1. 支持区间查询
2. 没有线段树那么强&＃xff0c;但是非常容易改成一维、二维、三维的结构
3. 只支持单点更新

原始数组 arr&＃xff1a;[3&＃xff0c; 1&＃xff0c; -2&＃xff0c; 3&＃xff0c; 6&＃xff0c; 0&＃xff0c; 9]
下标&＃xff1a; 1 2 3 4 5 6 7


准备一个 help 数组&＃xff08;相同长度的配成一对&＃xff09;
1&＃xff09;1位置的3长度为1&＃xff0c;前面没有长度为1的可以与之组成一对&＃xff0c;于是就拷贝自己的值 help[1] &＃61; arr[1] &＃61; 3 (长度为1)
2&＃xff09;2位置的1长度为1&＃xff0c;前面有长度为1的3可以与之组成一对&＃xff0c;于是 help[2] &＃61; arr[1] &＃43; arr[2] &＃61; 4 &＃xff08;长度为2&＃xff09;
3&＃xff09;3位置的-2长度为1&＃xff0c;前面没有长度为1的可以与之组成一对&＃xff0c;于是拷贝自己的值 help[3] &＃61; arr[3] &＃61; -2 (长度为1&＃xff09;
4&＃xff09;4位置的3长度为1&＃xff0c;前面有长度为1的-2可以与之组成一对&＃xff0c;二者相加 &＃61; 1&＃xff0c;此时已经长度为2&＃xff0c;而前面又有长度为2的可以与之组成一对&＃xff0c;于是 help[4] &＃61; arr[1] &＃43; arr[2] &＃43; arr[3] &＃43; arr[4] &＃61; 5 (长度为4&＃xff09;
5&＃xff09;5位置的6长度为1&＃xff0c;附近前面没有长度为1的&＃xff0c;于是 help[5] &＃61; arr[5] &＃61; 6 (长度为1&＃xff09;
6&＃xff09;6位置的0长度为1&＃xff0c;前面长度为1的6可以与之组成一对&＃xff0c;help[6] &＃61; arr[5] &＃43; arr[6] &＃61; 6 (长度为2&＃xff09;
7&＃xff09;7位置的9长度为1&＃xff0c;前面没有长度为1的可以与之组成一对&＃xff0c;于是help[7] &＃61; arr[7] &＃61; 9 &＃xff08;长度为1&＃xff09;

抛开数组中的值&＃xff0c;仅看 help 数组每个元素管理的原数组的下标&＃xff1a;

即 相同长度进行合并。

【规律1 &＃xff1a;help 数组的 index 管理的是 index 的二进制形式中的从右往左的第一个1拆开后加1到它自己这个范围的数】

例如 index &＃61; 010111000&＃xff0c;那么它管理的是原数组中的 010110001 ~ 010111000 这个范围的值&＃xff0c;即将 index 中从右往左数的第一个1拆开后加1到它自己的范围。

例 原数组 arr 下标从 1 到 8&＃xff0c;那么help数组中的 index &＃61; 8 的位置管理的是原数组1到8范围的值&＃xff0c;即 8 &＃61; 01000&＃xff0c;拆开1加1 &＃61; 00001&＃xff0c;所以管理的范围为 00001 ~ 01000 就是 1~8 范围。

同理 index &＃61; 12时&＃xff0c;12 &＃61; 01100&＃xff0c;第一个1去掉后加1 &＃61; 01001&＃xff0c;所以管理的范围是 01001 ~ 01100&＃xff0c;即原数组的9 ~ 12范围。

【利用help数组求原数组中1 ~ $i$ 位置的前缀和】

例1&＃xff1a;求原数组1 ~ 33 范围的前缀和&＃xff0c;33 的二进制形式是0100001&＃xff0c;那么就是help数组中 33 这个位置的值 a&＃xff0c;以及将33的二进制形式的最后一个1去掉得到的0100000&＃xff0c;对应到help数组中的该位置的 b&＃xff0c;将help数组中的这两个位置的值相加即是原数组 1 ~ 33 这个范围的前缀和。为什么正确呢&＃xff1f;因为help数组中的 33 就管理原数组的33位置的数&＃xff0c;而help数组中的32 位置管理1 ~ 32 位置的数&＃xff0c;所以二者相加就是1 ~ 33 范围的和。

例2&＃xff1a;求原数组 1 ~ $i$ 范围的前缀和&＃xff0c;其中 $i\&＃61;0101100110$&＃xff0c;那么就是取出 help 数组的如下位置的值进行累加&＃xff1a;

help[0101100110] &＃61; a&＃xff0c;拿出help数组中 $i$ 位置的数
help[0101100100] &＃61; b&＃xff0c;在上一步的基础上抹掉一个1
help[0101100000] &＃61; c&＃xff0c;在上一步的基础上抹掉一个1
help[0101000000] &＃61; d&＃xff0c;在上一步的基础上抹掉一个1
help[0100000000] &＃61; e&＃xff0c;在上一步的基础上抹掉一个1
直到没有 1 可以抹掉&＃xff0c;即index &＃61; 0 为止。


所以 sum[1...i] &＃61; a &＃43; b &＃43; c &＃43; d &＃43; e

为什么这个流程正确呢&＃xff1f;

当 $i\&＃61;0110100$ 时&＃xff0c;在上述流程中取的是 help 数组中的&＃xff1a;

help[0110100]&＃xff0c;管理的是原数组的 arr[0110001] ~ arr[0110100]

help[0110000]&＃xff0c;管理的是原数组的 arr[0100001] ~ arr[0110000]

help[0100000]&＃xff0c;管理的是原数组的 arr[0000001] ~ arr[0100000]

可见&＃xff0c;管理的原数组的范围全部是连续的&＃xff0c;所以就正确得到了原数组 1 ~ $i$ 的前缀和。

public class IndexTree {
// 下标从1开始&＃xff01;
public static class IndexTree {
private int[] tree;
private int N;
// 0位置弃而不用&＃xff01;
public IndexTree(int size) {
N &＃61; size;
tree &＃61; new int[N &＃43; 1];
}
// 根据index的位信息处理的&＃xff0c;index的二进制位中有多少个1就需要操作多少次&＃xff0c;得到每位的信息就是每次右移1位&＃xff0c;即除以2
// 所以时间复杂度 O(logn)
// 函数功能&＃xff1a;求1~index范围的累加和
// 所以如果要求 L 到 R的累加和 &＃61; 1~R的累加和 - 1~L-1的累加和
public int sum(int index) {
int ret &＃61; 0;
while (index > 0) {
ret &＃43;&＃61; tree[index];
index -&＃61; index & -index; //去掉最右侧的1
}
return ret;
}
// index & -index : 提取出index最右侧的1出来
// index : 0011001000
// index & -index : 0000001000
// x & (-x) &＃61; x & (~x &＃43; 1)
public void add(int index, int d) { //时间复杂度 O(logn)
//认为原始数组一开始全部为0&＃xff0c;现在要给index位置的数加d&＃xff0c;那么tree数组&＃xff08;即help数组&＃xff09;就会有位置的数受到影响
//比如原数组的 3 位置的数发生了变化&＃xff0c;那么 tree 数组中的哪些位置会受牵连呢&＃xff1f;
// 3 的二进制为011&＃xff0c;将最右侧的1加1 &＃61; 100&＃xff0c;即4
// 4 &＃61; 100 最右侧的1 加1 &＃61; 1000&＃xff0c;即8
// 8 &＃61; 1000 最右侧的1 加1 &＃61; 10000&＃xff0c;即16
// 即 011 -> 100 -> 1000 -> 10000 ->....
//规律&＃xff1a;只需要将发生更新位置的值的二进制的最右侧1加1 就能得到它影响tree数组哪些位置的值
while (index <&＃61; N) {
tree[index] &＃43;&＃61; d; //当前位置&＃43;d
index &＃43;&＃61; index & -index; //最右侧的1加1&＃xff0c;找出受到牵连的位置
}
}
}

//暴力解
public static class Right {
private int[] nums;
private int N;
public Right(int size) {
N &＃61; size &＃43; 1;
nums &＃61; new int[N &＃43; 1];
}
public int sum(int index) {
int ret &＃61; 0;
for (int i &＃61; 1; i <&＃61; index; i&＃43;&＃43;) {
ret &＃43;&＃61; nums[i];
}
return ret;
}
public void add(int index, int d) {
nums[index] &＃43;&＃61; d;
}
}
public static void main(String[] args) {
int N &＃61; 100;
int V &＃61; 100;
int testTime &＃61; 2000000;
IndexTree tree &＃61; new IndexTree(N);
Right test &＃61; new Right(N);
System.out.println("test begin");
for (int i &＃61; 0; i < testTime; i&＃43;&＃43;) {
int index &＃61; (int) (Math.random() * N) &＃43; 1;
if (Math.random() <&＃61; 0.5) {
int add &＃61; (int) (Math.random() * V);
tree.add(index, add);
test.add(index, add);
} else {
if (tree.sum(index) !&＃61; test.sum(index)) {
System.out.println("Oops!");
}
}
}
System.out.println("test finish");
}
}