///////////////////////////////////////
//  线段树解法 树中每结点的权值即所以其
//  子树上所加的权
///////////////////////////////////////

#include<stdio.h>
#include<math.h>
///////////////////////////////////////
// line is a struct of the tree node
///////////////////////////////////////
struct line
{
	int left;
	int right;
	int power;
};
double   lg2(double n)   
{   
    return   log(n)/log((double)2);   
}
///////////////////////////////////////
// judge a line from left to right and
// add the power to the proper position 
///////////////////////////////////////
void insert(int left,int right,int currentNodeIndex,int power,line* num)
{
	if(left==num[currentNodeIndex].left&&
	   right==num[currentNodeIndex].right)
    {
		num[currentNodeIndex].power=power+num[currentNodeIndex].power;
		//printf("num[%d].power=%d \n",currentNodeIndex,num[currentNodeIndex].power);
		return ;
	}
	if(num[currentNodeIndex].left==num[currentNodeIndex].right)
		return ;
	int mid=(num[currentNodeIndex].left+num[currentNodeIndex].right)/2;
	if(mid<left)
	{
		/*if(currentNodeIndex==0)
			currentNodeIndex=1;*/
		insert(left,right,(currentNodeIndex+1)*2,power,num);
	}
	else if(mid>=right)
	{		
		insert(left,right,currentNodeIndex*2+1,power,num);
	}
	else
	{	
		insert(left,mid,currentNodeIndex*2+1,power,num);
		/*if(currentNodeIndex==0)
			currentNodeIndex=1;*/
		insert(mid+1,right,(currentNodeIndex+1)*2,power,num);
		
	
	}
}

//////////////////////////////////////
// construct a line-tree from start to
// end
//////////////////////////////////////
int construct(int start,int end,line* num,int n)
{
	num[0].left=start;
	num[0].right=n-1;
	if(start==n-1)
	{
		scanf("%d",&num[0].power);
		return 0;
	}
	else
		num[0].power=0;
	int i=1;
	while(i!=2*n-1-(n-(end-start+1)))
	{
		if(i%2==1)
		{
			num[i].left=num[i/2].left;
			num[i].right=(num[i/2].left+num[i/2].right)/2;
		}
		else
		{
			num[i].left=num[i-1].right+1;
			num[i].right=num[i/2-1].right;
		}
		if(num[i].left==num[i].right)
			scanf("%d",&num[i].power);
		else
			num[i].power=0;
		i++;
	}
	//i=0;i<2*n-1;i++n-1
	/*for(i=0;i<2*n-1-(n-(end-start+1));i++)
		printf("%d ",num[i].power);
	printf("\n");*/
	return n-1;
}
///////////////////////////////////////
// output the sum from left to right 
///////////////////////////////////////
__int64 outResult(int left,int right,line* num)
{
	__int64 sum=0;
	for(int i=left;i<=right;i++)
	{
		int j=i;
		while(j!=0)
		{
			sum+=num[j].power;
			j=(j-1)/2;
		}
		sum+=num[j].power;
	}
	return sum;
}


int main()
{
	int N,Q;
	scanf("%d%d",&N,&Q);
	line *num;
	//////////////////////
	int n=N;
	double m=lg2((double)n);
	if(m!=(int)m)
		m=(int)m+1;
	n=pow(2,m);
	num=new line[2*n-1];
	///////////////////////
	int base=construct(0,N-1,num,n)-1;
	char letter;
	int a,b,c;
	while(Q!=0)
	{
		__int64 sum=0;
		getchar();
		scanf("%c%d%d",&letter,&a,&b);
		if(letter=='C')
		{
			getchar();
			scanf("%d",&c);
			insert(a-1,b-1,0,c,num);
		}
		else
		{
			a=a+base;
			b=b+base;
			sum=outResult(a,b,num);
			printf("%I64d\n",sum);
		}
		Q--;
		
	}
	delete []num;
	return 0;
}

• Re:谁能帮我看看这个代码,线段树处理的这道题,怎么就超时呢?跪求大牛给个解释吧 (58) ZYWei 2008-05-07 08:26:41
  • Re:大牛们,都说牛吃的是草,挤出来的是奶,跪求就挤些出来吧,赐教一下初学者^_^ (542) ZYWei 2008-05-07 08:29:56
  • 你再想一下如果插入线段吧...插入线段不要把线段全分开 (0) mmd 2008-05-07 10:21:03
  • Re:谁能帮我看看这个代码,线段树处理的这道题,怎么就超时呢?跪求大牛给个解释吧 (12) sanlu1 2009-03-17 21:36:36
• 我大体看了一下你的代码, 我觉得你应该好好想一下应该如何优美的实现线段树, 去找你们教主呗 (3526) mmd 2008-05-07 10:17:29