树状数组-详解
树状数组（Fenwick tree）
树状数组简介
树状数组主要用于查询任意两位之间的所有元素之和，而传统方法求区间和的方法如下：
用一个sum数组来储存1-i之间的区间和，那么如果要求从i到j的区间和的话，就用sum[i]-sum[j]，此时算法复杂度为n.
但是传统方法中，如果要更新一个元素值，那么此时更新就要把所有包含这个元素的区间全部遍历一遍，即算法复杂度为n
那么整个算法的复杂度为n^2
所以我们发现了树状数组这个算法，将更新与查找的算法复杂度降低至logn
lowbit函数
lowbit函数的工作是算出x的二进制的从右往左数第一个数的值
例如lowbit(6)要做的，就是：
- 把6转换为二进制数110
- 从左往右数第一个1的位置
- 此时lowbit(6)就=二进制的10
- 将（10）2转换为十进制
- 返回2
lowbit函数如下：
int lowbit(x){
return x & -x;
}
那么这个代码是什么意思呢？
&是按位与，按位与的运算为：如果两个数均为1，则返回1，否则，返回0.
那么x&(-x)是怎么做到我们想要的预期的呢？
在电脑中的运算是这样的：
例如lowbit(6)
- 输入2788，并将其保存入x中
- 将x转换为二进制码
101011100100 - 计算出1011的补码为
0101011100100 - 通过补码计算出-x为
1010100011100 - 按位与运算
0000000000100
因此，我们得出按位与的运算和lowbit的运算时一样的。
树状数组的保存
我们用两个数组来保存树状数组的结构：
tree数组和ans数组
其中，ans数组为输入的元素值
而tree数组的生成就要靠ans数组了
如图，即为tree数组
如何更新树状数组
上文说过，如果用传统方法来更新ans数组中的元素的话，会耗费大量的时间。那么我们不禁有个疑问了：树状数组是怎么缩短这个时间的呢？
例如，我们将ans[2]+3
那么我们将要更新1所在的所有区间。即：
我们需要更新所有的tree[2],tree[4],tree[8]的值
也就是说，当我们要对最底层的值进行更新时，那么它相应的父情节点储蓄的和也需要进行更新。
void update(int index, int value){
// len是数组tree的长度,,index为需要更新的数的下标，value为要更新的值
while(index <= len){
tree[index] += value;
index += lowbit(index);
}
}
此代码复杂度为logn
如何生成树状数组
在tree数组中，tree[i]并不表示1-i的区间和，而表示从i开始往前数lowbit(i)个数的区间和。
所以，我们需要一个算法来生成树状数组。
例如：查询从1-10的区间和：
这时，我们需要查找tree[8]+tree[10]的和
int sum(int index)
{
int result = 0;
while(index){
result += tree[index];
index -= lowbit(index);
}
return result;
}
此操作的算法复杂度为logn
如何查找树状数组
如果我们要计算tree中i-j的区间和，怎么办呢？
int p_sum(int i, int j){
return sum(j) - sum(i) + Ans[i];
}
算法复杂度为logn