1 #include <iostream> 2 #include <string.h> 3 #include <string> 4 #include <fstream> 5 #include <algorithm> 6 #include <stdio.h> 7 #include <vector> 8 #include <queue> 9 #include <set> 10 #include <cmath> 11 using namespace std; 12 const double eps = 1e-8; 13 const double pi=acos(-1.0); 14 const int INF=0x7fffffff; 15 unsigned long long uINF = ~0LL; 16 #define MAXN 200007 17 #define mod 1000000007 18 typedef long long LL; 19 int C[MAXN],a[MAXN],n,T=1,x,y; 20 int lowbit(int x) 21 { 22 return x&-x; 23 } 24 int sum(int x) 25 { 26 int ret=0; 27 while(x>0) 28 { 29 ret+=C[x];x-=lowbit(x); 30 } 31 return ret; 32 } 33 void add(int x,int d) 34 { 35 while(x<=n){ 36 C[x]+=d;x+=lowbit(x);} 37 } 38 39 int main() 40 { 41 42 while(scanf("%d",&n),n!=0) 43 { 44 if(T>1)printf(" "); 45 printf("Case %d: ",T++); 46 memset(a,0,sizeof(a)); 47 memset(C,0,sizeof(C)); 48 for(int i=1;i<=n;i++) 49 {scanf("%d",&a[i]);add(i,a[i]);} 50 string t; 51 while(cin>>t,t!="END") 52 { 53 if(t=="M"){ 54 scanf("%d%d",&x,&y); 55 printf("%d ",sum(y)-sum(x-1)); 56 } 57 else if(t=="S"){ 58 scanf("%d%d",&x,&y); 59 add(x,y-a[x]); 60 a[x]=y; 61 62 } 63 64 } 65 } 66 return 0; 67 }
树状数组