/* 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;
}

• Re:树状数组也超时的，那菜鸟只能无语，收山回林娶老婆！ (37) runformydream 2009-08-17 19:17:31
• Re:树状数组也超时的，那菜鸟只能无语，收山回林娶老婆！ (55) Liuzhaoliang 2009-08-18 08:50:22
  • Re:树状数组也超时的，那菜鸟只能无语，收山回林娶老婆！ (66) masque 2009-12-21 16:38:41
  • Re:树状数组也超时的，那菜鸟只能无语，收山回林娶老婆！ (82) frankvista 2010-08-08 23:56:36
    • Re:树状数组也超时的，那菜鸟只能无语，收山回林娶老婆！ (58) boy_lt 2010-09-17 23:29:41