acm算法之树状数组

//树状数组,关于其单点更改,区间求和,求前缀和,建树的操作
#include<stdio.h>
#include<string.h> 
int c[300]={0};//树状数组 
int a[300]={0};
int count;//原数组节点个数 
int lowbite(int m)
{
return m&(-m);

} 
void updata(int x,int value)
{
a[x]+=value;
while(x<=count)
{
	c[x]+=value;
	x+=lowbite(x);
}	
}
int sectsum(int m,int n)//注意,[1,m]减去[1,n]的区间表示的范围为[n+1,m] 
{
	int sum1=0,sum2=0;
	while(m>0)
	{
		sum1+=c[m];
		m-=lowbite(m);
	}
	while(n>0)
	{
		sum2+=c[n];
		n-=lowbite(n);
	}
	return sum2-sum1;
}
int main(void)
{
	int i,m,n,j,value;
	scanf("%d",&count);
	memset(c,0,sizeof(c));//申请空间,十分重要 
	scanf("%d %d",&m,&n);
	for(i=1;i<=count;i++)//注意,i要从一开始 ,才会满足上面推的二进制结论等等 
	{
		scanf("%d",&value);
		updata(i,value);
	}
	printf("%d\n",sectsum(m-1,n));
	return 0; 
}

上一篇:acm算法之并查集


下一篇:一句话***:ASPX篇