/* Note:Your choice is C IDE */
#include "stdio.h"
#include "string.h"

int n,q;
__int64 c[100001],sum;

int lowbit(int x)
{
	return x&(-x);
}

__int64 getsum(int x)
{
	__int64 sum=0;
	
	while( x>0 )
	{
		sum+=c[x];
		x-=lowbit(x);
	}
	return sum;
}

int updata(int x,int num)
{
	while( x<=n )
	{
		c[x]+=num;
		x+=lowbit(x);
	}
	return 0;
}

int main()
{
	__int64 a[100001];
	int i,j,x,y,d;
	char ch;
	
	//freopen("3243.txt","r",stdin);
	
	memset(c,0,sizeof(c));
	
	scanf("%d%d",&n,&q);
	for(i=1;i<=n;i++)
	{
		scanf("%I64d",&a[i]);
		updata(i,a[i]);
	}
		
	sum=0;
	
	while(q--)
	{
		scanf(" %c",&ch);
		
		if( ch=='C' )
		{
			scanf("%d%d%d",&x,&y,&d);
			while(x<=y)//每一点处都要加上 d
			{
				updata(x,d);
				x++;
			}
		}
		//计算区间 i - j 的和
		else
		{
			scanf("%d%d",&i,&j);
			sum=getsum(j) - getsum(i-1);
			printf("%I64d\n",sum);
		}
	}
	
    return 0;
}

• 你每次更新操作的复杂度是O(nlogn)的，还不如暴力 (0) 3xian 2009-08-17 13:54:04