首页 > 代码库 > 树状数组总结

树状数组总结

先谈一下线段树和树状数组的关系:

1.二者在复杂度上同级, 但是树状数组的常数明显优于线段树, 其编程复杂度也远小于线段树.
2.树状数组的作用被线段树完全涵盖, 凡是可以使用树状数组解决的问题, 使用线段树一定可以解决, 但是线段树能  够解决的问题树状数组未必能够解决.
树状数组的突出特点是其编程的极端简洁性, 使用lowbit技术可以在很短的几步操作中完成树状数组的核心操作,与之相关的便是其代码效率远高于线段树。
下面简单剖析一下树状数组:


“C[i]
















"C[i]表示A[i-2^k+1]到A[i]的和" 

1.我们可以这么理解,在数组c[i]中,
当i是2的倍数时(例如c[1],c[2],c[4]...),c[i]表示的是a[1]--a[i]的和
当i是奇数时(c[1],c[3],c[5]...),c[i]=a[i]
否则,c[i]=a[i-1]+a[i]


2.k 是i 在二进制时末尾0 的个数,2^k即是最小位的数值

例如i=101000,k=3,最小位是2^k=2^3=8


3. "2^k=i&(i^(i-1))",<=> "2^k=i&(-i)"       So->: i^(i-1)=-i?
证明:  
     i=6(10)=0000 0000 0000 0110
  i-1=5(10)=0000 0000 0000 0101
        i^(i-1)=0000 0000 0000 0011 
  i&(i^(i-1))=0000 0000 0000 0010


    i=6(10)=0000 0000 0000 0110
         -i=1111 1111 1111 1010
     i&(-i)=0000 0000 0000 0010
i&(i^(i-1))=i&(-i)  but,i^(i-1)!=-i  位运算不符合交换律!!!



code:

求t的最小位的数值


int Lowbit(int t) 
{
     return t & ( t ^ ( t - 1 ) );
}

求c[i]
 
void add(int i,int t)             
{
	while(i<=n)
	{
		tree[i]+=t;
		i+=lowbit(i);
	}
}


求所有树状数组的和


int sum(int m)                    
{
	int sum=0;
	while(m>0)
	{
		sum+=tree[m];
		m-=lowbit(m); 
	} 
	return sum;
}

//************************************版权所有***********转载请注明出处**********************************//



树状数组总结