> ///////////////////////////////////////
> //  线段树解法 树中每结点的权值即所以其
> //  子树上所加的权
> ///////////////////////////////////////
> 
> #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;
> }