数据结构之树状数组

树状数组原数组是a，c是a的树状数组可以发现这些规律C1=a1C2=a1+a2C3=a3C4=a1+a2+a3+a4C5=a5……C8=a1+a2+a3+a4+a5+a6+a7+a8……C2n=a1+a2+….+a2n树状数组对于序列a，我们设一个数组C◦C[i]=a[i–2k+1]+…+a[i]◦k为i在二进制下末尾0的个数C即为a的树状数组如何求k？2k=x&(x^(x-1))以6为例(6)10=(0110)2xor6-1=(5)10=(0101)2(0011)2and(6)10=(0110)2(0010)2树状数组1、用途树状数组是一种非常优雅的数据结构.当要频繁的对数组元素进行修改,同时又要频繁的查询数组内任一区间元素之和的时候,可以考虑使用树状数组.换句话说,树状数组最基本的应用:对于一个数组，如果有多次操作，每次的操作有两种（1）、修改数组中某一元素的值（2）、求和，求数组元素a[1]+a[2]+…a[num]的和。树状数组2、复杂度最直接的算法可以在O(1)时间内完成一次修改,但是需要O(n)时间来进行一次查询.而树状数组的修改和查询均可在O(log(n))的时间内完成.树状数组3、生成设a[1...N]为原数组,定义c[1...N]为对应的树状数组:c[i]=a[i-2^k+1]+a[i-2^k+2]+...+a[i]其中k为i的二进制表示末尾0的个数,所以2^k即为i的二进制表示的最后一个1的权值.所以2^k可以表示为n&(n^(n-1))或更简单的n&(-n).代码：intlowbit(intn){returnn&(-n);//orreturnn&(n^(n-1));}树状数组4、修改修改一个节点，必须修改其所有祖先，最坏情况下为修改第一个元素，最多有log(n)的祖先。对a[n]进行修改后,需要相应的修改c数组中的p1,p2,p3...等一系列元素，其中p1=n,p(i+1)=pi+lowbit(pi)所以修改原数组中的第n个元素可以实现为:voidModify(intn,intdelta){while(n=N){c[n]+=delta;n+=lowbit(n);}}树状数组5、求和当要查询a[1],a[2]...a[n]的元素之和时,需要累加c数组中的q1,q2,q3...等一系列元素其中q1=n,q(i+1)=qi-lowbit(qi)所以计算a[1]+a[2]+..a[n]可以实现为:intSum(intn){intresult=0;while(n!=0){result+=c[n];n-=lowbit(n);}returnresult;}树状数组为什么是效率是log(n)的呢？以下给出证明：n=n–lowbit(n)这一步实际上等价于将n的二进制的最后一个1减去。而n的二进制里最多有log(n)个1，所以查询效率是log(n)的。换句话说:若需改变a[i]，则c[i]、c[i+lowbit(i)]、c[i+lowbit(i)+lowbit(i+lowbit(i)]……就是需要改变的c数组中的元素。若需查询s[i]，则c[i]、c[i-lowbit(i)]、c[i-lowbit(i)-lowbit(i-lowbit(i))]……就是需要累加的c数组中的元素。6、与线段树的比较树状数组是一个可以很高效的进行区间统计的数据结构。在思想上类似于线段树，比线段树节省空间，编程复杂度比线段树低，但适用范围比线段树小。线段树树状数组7、扩展--二维树状数组一维树状数组很容易扩展到二维，二维树状数组如下所示：C[x][y]=sum(A[i][j])其中，x-lowbit[x]+1=i=x且y-lowbit[y]+1=j=y树状数组（例）HDU1166#includecstdio#includecstring#includeiostream#includealgorithmusingnamespacestd;#defineN50005intn;inta[N],c[N];intlowbit(intx){return(x&-x);}voidadd(inti,intw){while(i=n){c[i]+=w;i=i+lowbit(i);}}intsum(inti){intsum=0;while(i0){sum+=c[i];i=i-lowbit(i);}returnsum;}intmain(){intcas=0;intt,w,u,v;charst[100];scanf(%d,&t);while(t--){scanf(%d,&n);for(inti=0;i=n;i++)a[i]=c[i]=0;for(inti=1;i=n;i++){scanf(%d,&w);add(i,w);}printf(Case%d:\n,++cas);while(scanf(%s,st),strcmp(st,End)!=0){scanf(%d%d,&u,&v);if(strcmp(st,Query)==0){printf(%d\n,sum(v)-sum(u-1));}elseif(strcmp(st,Add)==0){add(u,v);}elseif(strcmp(st,Sub)==0){add(u,-v);}}}}练习题:HDU1541155623522155POJ2299