1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 int n,C[50005]; 6 //-------------------------- 7 int lowbit(int x){ 8     return x&-x; 9 }10 int sum(int x){11     int ret=0;12     while(x>0){13         ret+=C[x];14         x-=lowbit(x);15     }16     return ret;17 }18 void add(int x,int d){19     while(x<=n){20         C[x]+=d;21         x+=lowbit(x);22     }23 }24 //--------------------------25 int main(){26     int T;27     scanf("%d",&T);28     int kases=1;29     int i,j;30     int a;31     for(;kases<=T;kases++){32         memset(C,0,sizeof(C));  33         scanf("%d",&n);34         for(i=1;i<=n;i++){35             scanf("%d",&a);36             add(i,a);37         }38         char str[10];39         printf("Case %d:\n",kases);40         bool ok=1;41         while(ok){42             scanf("%s",str);43             switch(str[0]){44             case 'Q':45                 scanf("%d%d",&i,&j);46                 printf("%d\n",sum(j)-sum(i-1));47                 break;48             case 'A':49                 scanf("%d%d",&i,&j);50                 add(i,j);51                 break;52             case 'S':53                 scanf("%d%d",&i,&j);54                 add(i,-j);55                 break;56             case 'E':57                 ok=0;58                 break;59             default:break;60             }61         }62     }return 0;63 }
       
      
     

 

1 #include
     
       2 #include
      
        3 using namespace std; 4 #define maxn 100005 5 class Node{ 6 public: 7     int l,r; 8     int add;//附加值 9     int sum;10 }node[maxn];11 int getRight(int n){
   //获得满足2^x>=n的最小x[从0层开始,给编号获得层数]12     return ceil(log10(n*1.0)/log10(2.0));13 }14 void build(int l,int r,int num){
   //输入区间[1,2^getRight(n)],num=1建树15     if(l==r){16         node[num].l=node[num].r=l;node[num].add=0;node[num].sum=0;17         return;18     }19     node[num].l=l;node[num].r=r;node[num].add=0;node[num].sum=0;20     build(l,(l+r)/2,num*2);21     build((l+r)/2+1,r,num*2+1);22 }23 void add(int o,int l,int r,int v){
   //从o节点开始递归[只要调用时o=1即可]在区间[l,r]全部加v24     if(l<=node[o].l && r>=node[o].r){
   //全覆盖[递归边界]25         node[o].add+=v;26     }else{27         int M=node[o].l+(node[o].r-node[o].l)/2;28         if(r<=M)add(o*2,l,r,v);29         else if(l>M)add(o*2+1,l,r,v);30         else{31             add(o*2,l,M,v);32             add(o*2+1,M+1,r,v);33         }34     }35     //维护节点o36     if(node[o].l!=node[o].r){
   //如果区间只是一个元素就不算37         node[o].sum=node[2*o].sum+node[2*o+1].sum;38     }else node[o].sum=0;39     node[o].sum+=node[o].add*(node[o].r-node[o].l+1);40 }41 42 //这里addadd是从上往下这条路的累计addadd值[一同回溯记录这条路节点所有add之和，减少了一次回溯累加add值]43 //初始时直接令其为044 int sum=0;45 void ask(int o,int l,int r,int addadd){
   //从o节点开始递归[只要调用时o=1即可]在区间[l,r]的和46     if(l<=node[o].l && r>=node[o].r){
   //全覆盖[递归边界]47         sum+=(node[o].sum+addadd*(node[o].r-node[o].l+1));48     }else{49         int M=node[o].l+(node[o].r-node[o].l)/2;50         if(r<=M)ask(o*2,l,r,node[o].add+addadd);51         else if(l>M)ask(o*2+1,l,r,node[o].add+addadd);52         else{53             ask(o*2,l,M,node[o].add+addadd);54             ask(o*2+1,M+1,r,node[o].add+addadd);55         }56     }57 }58 int main(){59     int T;60     scanf("%d",&T);61     int kases=1;62     int i,j;63     int a;64     for(;kases<=T;kases++){65         int N;66         scanf("%d",&N);67         build(1,1<