很久没做线段树的题目了。自己想想延迟标记怎么弄...
#include<iostream>
#define MAXN 55555
using namespace std;int tree[MAXN<<2];void pushUp( int rt )
{tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}void build( int l,int r,int rt )
{if( l==r ){scanf( "%d",&tree[rt] );return ;}int m=(l+r)/2;build( l,m,rt<<1 );build( m+1,r,rt<<1|1 );pushUp( rt );
}int query( int L,int R,int l,int r,int rt )
{if( L<=l&&r<=R )return tree[rt];int m=(l+r)/2;int ret=0;if( m>=R )ret+=query( L,R,l,m,rt<<1 );if( L>=m+1 )ret+=query( L,R,m+1,r,rt<<1|1 );if( L<m+1 && m<R ){ret+=query( L,R,l,m,rt<<1 );ret+=query( L,R,m+1,r,rt<<1|1 );}return ret;
}void add( int pt,int v,int l,int r,int rt )
{if( l==r ){tree[rt]+=v;return ;}int m=(l+r)/2;if( pt<=m )add( pt,v,l,m,rt<<1 );elseadd( pt,v,m+1,r,rt<<1|1 );pushUp(rt);
}int main()
{int T,cases=1;scanf( "%d",&T );while( T-- ){printf( "Case %d:\n",cases++ );int N;scanf( "%d",&N );build( 1,N,1 );char str[111];getchar();while( gets(str) ){int n1,n2;if( sscanf(str,"Query %d %d",&n1,&n2) )printf( "%d\n",query(n1,n2,1,N,1) );else if( sscanf(str,"Sub %d %d",&n1,&n2) )add( n1,-n2,1,N,1 );else if( sscanf(str,"Add %d %d",&n1,&n2) )add( n1,n2,1,N,1 );else if( strcmp(str,"End")==0 )break;}}return 0;
}