树状数组和线段树的简要描述

最近在看树状数组和线段树，没完整看完，把目前学的暂时记录，后续再补。

线段树和树状数组都是对区间操作的数据结构

 1 #define ls (x<<1)
 2 #define rs (x<<1|1)
 3 using namespace std;
 4 const int N=1e5+5;
 5 int sum[N<<2]//元素a数组的N和树上节点数转换关系是4n-1,所以开4倍算上最后一层空节点，因为其他函数要访问；
 6 int t[N<<2],a[N]; 
 7 void update(int x)
 8 {
 9     sum[x]=sum[ls]+sum[rs]; 
10 }
11 void build(int l,int r,int x)
12 {
13     if(l==r)
14     {
15         t[x]=a[l];//数节点存储的数组元素值；
16         return; 
17     }
18     int mid=l+r>>1;
19     build(l,mid,ls);
20     build(mid+1,r,rs);
21     update(x);//这里的功能暂时是区间求和 
22 }

树状数组核心思想是利用某个数的二进制进行sum求和

如10的二进制1010，有两个1，故可以拆分为2个集合来求1-10的区间和；

记录数组c[n+1], 前10个元素和c[10]   1010是由c[10]+c[8]两个子集和相加获得；

lowbit 是i&(-i)获取二进制第一个1的十进制数，如1010 lowbit后是0010=2；

大概知道怎么求和了，后面就是怎么获取c数组，有c数组我们可以在log的时间内区间求和

C数组获取就是更新树，对于每一个a[i]我们要考虑哪些子集包含a[i],后续的操作会对所有包含a[i]的子集进行更新

基于这样的思想

对于101000这样的数无论101后面是什么01的组合都不能使得101000包含在这些组合里，因为lowbit的最小结果是变成101000而包含元素起点是101001；

所以由枚举思想我们+lowbit发现变成110000 这个集合lowbit后是100001-110000这个区间101000包含在此，不难发现对于

110000，11后的0随便01组合最小值为110001-组合数>101000;

所以lowbit的正确性和唯一性我们都能保证，具体证明别处也有可以去看看，下面上代码；

 1 int c[N],a[N];
 2 inline int lowbit(int i){return i&(-i);}
 3 //不要从0开始lowbit(0)是0下面会T；
 4 void update(int i,int val)
 5 {
 6     for(;i<=N;i+=lowbit(i))c[i]+=val;
 7 }
 8 //初始化就是 
 9 for(int i=1;i<=N;i++)update(i,a[i]); 
10 //先更到这后面在更；