> #include<iostream>
> using namespace std;
> 
> #define MAXM 100000
> 
> struct 
> {
> 	int l,r;
> 	 __int64 sum,crease;//超过整数的范围
> }tree[MAXM*4+1];
> 
> void build(int left,int right,int num)
> {
> 	 int d;
>      tree[num].l=left;tree[num].r=right;
> 	 if(tree[num].l==tree[num].r){ tree[num].crease=0;cin>>d;tree[num].sum=d;return;}
> 	 int mid=(tree[num].l+tree[num].r)>>1;
> 	 build(tree[num].l,mid,num<<1);
> 	 build(mid+1,tree[num].r,num<<1|1);
> 	 tree[num].sum=tree[num<<1].sum+tree[num<<1|1].sum;
>      tree[num].crease=0;
> }
> 
> int query(int left,int right,int num)
> {
>      if(left==tree[num].l&&tree[num].r==right)return tree[num].sum;
> 	 int mid=(tree[num].l+tree[num].r)>>1;
> 	 if(right<=mid)return query(left,right,num<<1);
> 	 else if(mid<left)return query(left,right,num<<1|1);
> 	 else return (query(left,mid,num<<1)+query(mid+1,right,num<<1|1));
> }
> 
> void addnew(int left,int right,int add,int num)
> {
>     if(tree[num].l==left&&tree[num].r==right)
> 	{tree[num].crease+=add;return;}
>     int mid=(tree[num].l+tree[num].r)>>1;
> 	if(right<=mid) addnew(left,right,add,num<<1);
> 	else if(mid<left) addnew(left,right,add,num<<1|1);
> 	else 
> 	{
> 		addnew(left,mid,add,num<<1);
> 		addnew(mid+1,right,add,num<<1|1);
> 	}
> 	tree[num].sum=tree[num<<1].sum+tree[num<<1].crease*(tree[num<<1].r-tree[num<<1].l+1);
> 	tree[num].sum+=tree[num<<1|1].sum+tree[num<<1|1].crease*(tree[num<<1|1].r-tree[num<<1|1].l+1);
> }
> 
> int main()
> {
> 	int N,M,i,j,p;
> 	char c;
> 	cin>>N>>M;
> 	build(1,N,1);
> 	for(int k=0;k<M;k++) 
> 	{
> 		 scanf("%c",&c);
> 		 if(c=='Q')
> 		 {
> 			 
> 			 scanf("%d%d",&i,&j);
> 			 printf("%d\n",query(i,j,1));
> 				 
> 		 }
>          else
> 		 {
> 			 scanf("%d%d%d",&i,&j,&p);
>              addnew(i,j,p,1);
> 		 }
> 	}
> 	return 0;
> }

• Re:这道3468题希望有人帮我看看，我是初学线段树的，这道题做了好久了，但是addnew更新哪里总有错误，愁死了，江湖救急，大家帮帮忙 (0) Tune 2012-05-12 21:06:27