【线段树（单点修改，区间求和）】HDU1166 - 敌军布阵

hdu1166 敌兵布阵，单点修改，区间求和。

【ATTENTION】MAXN要开成节点数的4倍，开得不够会提示TLE。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #define lson l,m,root<<1

 #define rson m+1,r,root<<1|1

 using namespace std;

 const int MAXN=*+;

 int n;

 int sum[MAXN];

 void pushUP(int root)

 {

     sum[root]=sum[root<<]+sum[root<<|];

 }

 void build(int l,int r,int root)

 {

     if (l==r)

     {

         scanf("%d",&sum[root]);

         return;

     }

     int m=(l+r)>>;

      build(lson);

     build(rson);

     pushUP(root);

 }

 void update(int p,int delta,int l,int r,int root)

 {

     if (l==r)

     {

         sum[root]+=delta;

         return;

     }

     int m=(l+r)>>;

     if (p<=m) update(p,delta,lson);

     if (p>m) update(p,delta,rson);

     pushUP(root);

 }

 int query(int L,int R,int l,int r,int root)

 {

     int result=;

     if (l>=L && r<=R)

     {

         return sum[root];

     }

     int m=(l+r)>>;

     if (L<=m) result+=query(L,R,lson);

     if (R>m) result+=query(L,R,rson);

     return result;

 }

 int main()

 {

     int t;

     scanf("%d",&t);

     for (int kase=;kase<t;kase++)

     {

         cout<<"Case "<<kase+<<":"<<endl;

         scanf("%d",&n);

         build(,n,);

         char s[];

         while (scanf("%s",s))

         {

             if (s[]=='E') break;

             int a,b;

             scanf("%d%d",&a,&b);

             if (s[]=='A') update(a,b,,n,);

             if (s[]=='S') update(a,-b,,n,);

             if (s[]=='Q') cout<<query(a,b,,n,)<<endl;

         }

     }

     return ;

 }