今天回顾了一下树状数组的有关内容。
可以说是今天才看懂树状数组的意思吧。。对之前的理解毫无印象..
现在这里马克一下
树状数组：
树状数组是用于存储数据的一种特殊的数据结构。具体的形状如下图：
a数组是我们宏观普遍出现的数组形式，c就是相对的树状数组。
二进制条件下：
a[0]到a[1110]的和=c[1110]+c[0110]+c[0010];
修改a[1]时，受到影响的有c[1],c[10],c[100],c[1000].....
对于这样的运算，我们用到了&来计算。
lowbit();的作用是去掉高位1 （1100就是0100，1110就是0010，1000就是本身）
lowbit（k）=k&-k;
所以修改和读取的操作分别是：
void add(int k,int num) { while(k<=n) { tree[k]+=num; k+=k&-k; } } //修改 int read(int k)//1~k的区间和 { int sum=0; while(k) { sum+=tree[k]; k-=k&-k; } return sum; } //读取
当然，有一些时候数据会让你难以使用树状数组。比如，求区间中不同的数的个数（多次修改，多次询问），这个时候就可以用莫队来解决了~~
等我看完莫队再来补笔记....
树状数组时间复杂度O（lg n）