1 #include <algorithm>  2 #include <iostream>  3 #include <sstream>  4 #include <cstdlib>  5 #include <cstring>  6 #include <cstdio>  7 #include <string>  8 #include <bitset>  9 #include <vector> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <list> 14 //#include <map> 15 #include <set> 16 using namespace std; 17 /***************************************/ 18 #define ll long long 19 #define int64 __int64 20 #define PI 3.1415927 21 /***************************************/ 22 const int INF = 0x7f7f7f7f; 23 const double eps = 1e-8; 24 const double PIE=acos(-1.0); 25 const int d1x[]= {0,-1,0,1}; 26 const int d1y[]= {-1,0,1,0}; 27 const int d2x[]= {0,-1,0,1}; 28 const int d2y[]= {1,0,-1,0}; 29 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 30 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 31 const int dirx[]= {-1,1,-2,2,-2,2,-1,1}; 32 const int diry[]= {-2,-2,-1,-1,1,1,2,2}; 33 /*vector <int>map[N];map[a].push_back(b);int len=map[v].size();*/ 34 /***************************************/ 35 void openfile() 36 { 37     freopen("data.in","rb",stdin); 38     freopen("data.out","wb",stdout); 39 } 40 priority_queue<int> qi1; 41 priority_queue<int, vector<int>, greater<int> >qi2; 42 /**********************华丽丽的分割线,以上为模板部分*****************/ 43 const int M=50010; 44 struct tree 45 { 46     int sum;  //该区间的总和 47     int left,right;  //记录区间的左右闭区间坐标 48 } node[M*4];  //需开四倍的空间大小 49 int p[M];  //储存每个地点的人数数量 50 int cnt; 51 void build__tree(int id,int l,int r)  //建树 52 { 53     int mid=(l+r)/2; 54     node[id].left=l;   //初始化赋值区间的坐标 55     node[id].right=r; 56     if (l==r) 57     { 58         node[id].sum=p[l];  //初始化区间节点的val值 59         return ; 60     } 61     build__tree(id*2,l,mid);  //左孩子 62     build__tree(id*2+1,mid+1,r); //右孩子 63     node[id].sum=node[id*2].sum+node[id*2+1].sum;  //通过递归将各个区间节点val更新 64 } 65 int query(int id,int l,int r)  //查询区间的总和 66 { 67     int mid=(node[id].left+node[id].right)/2; 68     if (node[id].left==l&&node[id].right==r) 69         cnt+=node[id].sum;  //找到完全覆盖的区间将该区间的val加和。 70     else if (l>mid)   //[l，r]在右孩子部分 71         query(id*2+1,l,r); 72     else if (r<=mid) // [l，r]在左孩子部分 73         query(id*2,l,r); 74     else  //[l，r]区间，左右孩子都有分别递归。 75     { 76         query(id*2,l,mid); 77         query(id*2+1,mid+1,r); 78     } 79 } 80 void updata(int id,int pos,int val)  //从上向下寻找节点，找到节点后然后从下往上更新节点的val值 81 { 82     if (node[id].left==pos&&node[id].right==pos)//找到该节点 83     { 84         node[id].sum+=val; 85         return ; 86     } 87     int mid=(node[id].left+node[id].right)/2; 88     if (pos<=mid)  //节点在左孩子部分 89         updata(id*2,pos,val); 90     else //节点在右孩子部分 91         updata(id*2+1,pos,val); 92     node[id].sum=node[id*2].sum+node[id*2+1].sum; //从下往上更新区间节点的值 93 } 94 int main() 95 { 96     int cas; 97     scanf("%d",&cas); 98     int n; 99     char s[10];100     int flag=0;101     while(cas--)102     {103         int i,j;104         scanf("%d",&n);105         for(i=1; i<=n; i++)106             scanf("%d",&p[i]);107         build__tree(1,1,n);108         printf("Case %d:\n",++flag);109         while(scanf("%s",s)!=EOF)110         {111             int x,y;112             if (s[0]==‘Q‘)113             {114                 scanf("%d%d",&x,&y);115                 cnt=0;116                 query(1,x,y);117                 printf("%d\n",cnt);118             }119             else if (s[0]==‘A‘)120             {121                 scanf("%d%d",&x,&y);122                 updata(1,x,y);123             }124             else if (s[0]==‘S‘)125             {126                 scanf("%d%d",&x,&y);127                 updata(1,x,-y);128             }129             else130                 break;131         }132     }133     return 0;134 }