acm算法之树状数组

本文主要是介绍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算法之树状数组的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！