树状数组处理：在一个数量为n的序列中，频繁的有以下两种需求：

1、更改某个位置的数据

2、询问某个区间的数据和

10 5

1 2 3 4 5 6 7 8 9 10

1 1 5

0 1 3

0 4 8

1 7 5

0 4 8

11 30 35

求数组的区间和：前缀和

a   1 2 3 4  5  6  7  8  9  10

sum 1 3 6 10 15 21 28 36 45 55

i~j:sum[j]-s[i];

将数组化成树形数组

a：1  2  3  4  5  6  7  8  9  10

t：1  3  3  10 5  11 7  36 9  19        

求前x位的和：get(x)

需要知道下标的二进制的最低位1的值：lowbit()运算

设n=44:101100

     100

将101100取反->010011再+1->010100

将结果与原数据进行&运算：101100&010100=100

取反+1的操作与-n的二进制相同

所以lowbit()运算就相当于 x=x&-x;

19:10011->1 10011-1=10010->10 10010-10=10000->10000 10000-10000=0结束

int get(int x){

   int ans=0;

   for(int i=x;i!=0;i-=i&-i){

       ans+=t[i];

   }

   return ans;

}

求i～j之间的数据和：get(j)-get(i-1);

x->x+lowbit(x)

void change(int x,int k){

   for(int i=x;i<=n;i+=i&-i){

       t[i]+=k;

   }

}

原解法：O(n2)

树状数组：O(nlogn)

涉及到的知识点：lowbit运算，前缀和，树形思维

a数组代表原数组

t数组代表树状数组

t[x]以x为根时所有叶子结点的和

t[x]节点代表的数据宽度为lowbit(x)

如果当前节点为x，则它的父节点为x+lowbit(x)

通过原数组a，构建树状数组t

vector<int> build_BIT(vector<int> a){

   vector<int> t(a.size()+1,0);

   for(int i=0;i<n;i++){

       t[i+1]=a[i];

       int j=i+1+lowbit(i+1);

       if(j<=n){

           t[j]+=t[i+1];

       }

   }

   return t;

}

树状数组题型：

1、更改单点的数据，查找单点的值

2、更改单点的数据，查找区间的和

3、更改区间的数据，查找单点数据（需要差分数组）

4、更改区间的数据，查找区间的值

作业：数据结构-树状数组：例1，时间足够的话完成例3