树状数组.txt

介绍了树状数组的实现方法及代码

对于序列a，我们设一个数组C定义C[t] = a[t – 2^k + 1] + … + a[t]，k为t在二进制下末尾0的个数。 
C[t] 管辖着2^k个数据， 比如说t=2时，则k=1，就管理着2个数据；当t=8时，则k=3，就管理着8个数据，依次为a[t-2^k+1]+...
+a[t]
注：数组C是用来管理数组a的， 
K的计算可以这样: 
2^k=t and (t xor (t-1)) 
以t=6为例 
        (6)10=(0110)2 
xor    6-1=(5)10=(0101)2 
           (0011)2 
and          (6)10=(0110)2 
              0010)2 
比如要给in[3]加上2，那么(11)2后面没零，那就加3+1=4，使in[4]也加上2，然后(100)2后面有2个零，那么使4+4=8，在in[8]上也加上1， 然后(1000)2，然后8+8=16 使in[16] 也加上1 ，...



#include<iostream>
#include<stdio.h>
using namespace std;
int in[7];
int a[7]={0,1,2,3,4,5,6};
int Lowbit(int t) 
{ 
    return t & ( t ^ ( t - 1 ) ); 
} 
int Sum(int end)  //求总和
{ 
	int sum = 0; 
	while(end > 0) 
	{ 
		sum += in[end]; 
		end -= Lowbit(end);  //去掉最后一个“1”
	} 
	return sum; 
} 
void plus(int pos , int num) //修改某个数
{ 
    while(pos <= 6) 
    { 
          in[pos] += num; 
          pos += Lowbit(pos); //依次向上级加上这个数
    } 
} 

int main()
{
	int i;
	memset(in,0,sizeof(in));
	for(i=1;i<=6;i++)
		plus(i,a[i]);
 //如果要求j到k之间的和，则=Sum(k)-Sum(j-1)
}