线段树模板

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 const int N=50000+11;
 6 int a[N<<2];
 7 void getdown(int rt)
 8 {
 9     a[rt]=a[rt<<1]+a[rt<<1|1];
10 }
11 void build(int l,int r,int rt)
12 {
13     if(l==r)
14     {
15         scanf("%d",&a[rt]);
16         return ;
17     }
18     int mid=(l+r)>>1;
19     build(lson);
20     build(rson);
21     getdown(rt);
22 }
23 void updata(int p,int x,int l,int r,int rt)
24 {
25     if(l==r)
26     {
27         a[rt]+=x;
28         return ;
29     }
30     int mid=(l+r)>>1;
31     if(p<=mid)    updata(p,x,lson);
32     else        updata(p,x,rson);
33     getdown(rt);
34 }
35 int Q(int L,int R,int l,int r,int rt)
36 {
37     if(L<=l&&R>=r)    return a[rt];
38     int ans=0;
39     int mid=(l+r)>>1;
40     if(L<=mid)    ans+=Q(L,R,lson);
41     if(R>mid)    ans+=Q(L,R,rson);
42     return ans;
43 }
44 int main()
45 {
46     int t,cas=0,n;
47     scanf("%d",&t);
48     while(t--)
49     {
50         scanf("%d",&n);
51         build(1,n,1);
52         char s[10];int x,y;
53         printf("Case %d:\n",++cas);
54         while(scanf("%s",s)&&s[0]!=‘E‘)
55         {
56             scanf("%d%d",&x,&y);
57             if(s[0]==‘Q‘)    printf("%d\n",Q(x,y,1,n,1));
58             if(s[0]==‘A‘)    updata(x,y,1,n,1);
59             if(s[0]==‘S‘)    updata(x,-y,1,n,1);
60         }
61     }
62     return 0;
63 }