树状数组是什么
树状数组是一种非常适合于求前缀和的工具（或者是其他的一些有关前缀的东西，例如区间最大值等等） 尤其是涉及到单点修改的操作的时候 如果是用普通的线性数组 和 线性的求和数组的话 复杂度会达到O(n)
而使用树状数组 则可以将这个复杂度 降低至O(logn)
怎么使用树状数组
假设用一个a数组来储存这个区间中的元素（索引从1开始）
树状数组的最基本的使用 主要有四个部分组成
- int c[maxn] 一个数组 用来储存前缀和
- int lowbit(int x) 一个函数 用来求下标
- void update(int position,int value) 一个函数 用来进行单点修改
- int get_sum(int x) 一个函数 用来求从区间左端点 到 x 的元素的和
树状数组储存的原理
——利用lowbit()函数来计算下标
lowbit是什么
：一个二进制数从右到左的第一个1
就比如说 十进制数12 转化为二进制数就是 1100 那么它的从右到左的第一个1就是 100 转化为十进制数就是4
这个操作可以用lowbit()函数非常快的求出来
代码如下：
int lowbit(int x){
return x&(-x);
}
这个的原理不讲 举个例子看一看：
就比如说之前的那个12的例子
-12 的补码形式是 1000……0000100
12 的补码形式是 0000……0001100
那么在进行位与操作 求得答案 100 转化为十进制也就是 4
储存
知道了lowbit之后 就可以用这个来创建一个树状数组了
前面说了 在这里用一个c数组来储存
规定 c[i] 这个元素 储存的是 区间内 第i-lowbit(i)+1 个元素 到第 i个元素的和
那么对于区间中的某一个元素a[i]而言 它对那些c数组中的元素产生了影响呢？
1、首先c[i]这个元素肯定被影响到了 因为这个元素储存的就直接是 区间内 第i-lowbit(i)+1 个元素 到第 i个元素的和
而且所有索引小于i的元素都没有被影响到
2、然后 第i+lowbit(i)个元素也被影响到了 c[i+lowbit(i)]
因为可以计算出来 lowbit(i+lowbit(i)) 必然大于等于 lowbit(i) 这个非常浅显因为i加上一个lowbit(i)之后 最后一个1的位置必然往前进一位 故再求得的 lowbit(i+lowbit(i)) 会更大
例如一个数i =……1000
它的lowbit(i)=1000
故i+lowbit(i)=……10000
再求lowbit(i+lowbit(i))=10000 > 1000
3、那么在第i个元素 到第 i+lowbit(i) 个元素之间是否有元素被影响到呢？
答案是没有。
我们可以假设有一个数i = ……1000
那么这个数i 求lowbit(i)=1000
那么i+lowbit(i) =……10000
那么在i到i+lowbit(i)之间的所有的数就是
……1001 ~ ……1111
这些数（设为x） 所储存的和的左端点为 x-lowbit(x)+1 > i
所以 都必定取不到i这个数
4、再根据数学归纳法的递推原理
while(){
//在其中添加逻辑
i=i+lowbit(i);
}
这个循环里面的所有元素均会被影响到，但是这样必然进入一个死循环 无法跳出
但是其实我们并不需要处理这么多元素 只需要处理到这个区间的右端点就可以了
于是这个循环可以写成这样：
while(i<=right_restrain){
//在其中添加逻辑
i+=lowbit(i);
}
单点更新——update()
知道了树状数组的储存原理 以及每一个元素储存了区间中那哪一些值之后 进行单点修改操作就很简单了
已知 将要进行修改的元素的位置 并且知道它的变化量
void update(int position,int value){
//表示要将区间position的元素的值增加value（value可以是负数）
while(position<=right_restrain){
c[position]+=value;
position+=lowbit(position);
}
}
区间求和
因为c数组中的元素c[i]储存 的是区间内 第i-lowbit(i)+1 个元素 到第 i个元素的和
故如果我们要求从这个区间的第一个元素加到第i个元素的和
就可以这样做
c[i]+c[i-lowbit(i)]+……
最后直到i-lowbit(i)等于0为止（因为对于上一个元素已经加到了 i-lowbit(i)+1 而i-lowbit(i)又等于0 所以就表示已经加到了区间的第一个元素了）
代码如下：
int get_sum(int position){
//表示要求区间中 第一个元素到第position个元素的和
int sum=0;
while(position){
sum+=c[position];
position-=lowbit(position);
}
return sum;
}
至于要求第i个元素到第j个元素的和（i<j）就很简单了
int getSum(int i,int j){
return get_sum(j)-get_sum(i-1);
}
这样最简单的树状数组的单点修改和区间求和操作就完成了
树状数组经典入门例题讲解
树状数组进阶
区间最值
二维树状数组