线段树

#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; int sum,n; struct node {     int l,r,n;//记录下左右边界 } a[1000000]; void init()//新建一个线段树 {     int i,k;     for(k = 1; k<n; k<<=1);     for(i = k; i<2*k; i++)     {         a[i].l = a[i].r = i-k+1;         a[i].n = 0;     }     for(i = k-1; i>0; i--)     {         a[i].l = a[2*i].l;         a[i].r = a[2*i+1].r;         a[i].n = 0;     } } void insert(int i,int x,int m)//线段树的插入 {     if(x>=a[i].l && x<=a[i].r)         a[i].n+=m;     if(a[i].l == a[i].r)         return ;     int mid = (a[i].l+a[i].r)/2;     if(x>mid)         insert(2*i+1,x,m);     else         insert(2*i,x,m); } void find(int x,int y,int i)//线段树的查询 {     if(a[i].l == x && a[i].r == y)     {         sum+=a[i].n;         return ;     }     if(a[i].l == a[i].r)         return ;     int mid = (a[i].l+a[i].r)/2;     if(x>mid)         find(x,y,2*i+1);     else if(y<=mid)         find(x,y,2*i);     else     {         find(x,mid,2*i);         find(mid+1,y,2*i+1);     } } int main() {     int t,cas = 1,x,y,i,j,k;     char str[10];     scanf("%d",&t);     while(t--)     {         scanf("%d",&n);         init();         for(i = 1; i<=n; i++)         {             scanf("%d",&k);             insert(1,i,k);         }         printf("Case %d:\n",cas++);         while(scanf("%s",str) && str[0]!='E')         {             scanf("%d%d",&x,&y);             if(!strcmp(str,"Add"))                 insert(1,x,y);             else if(!strcmp(str,"Sub"))                 insert(1,x,-y);             else if(!strcmp(str,"Query"))             {                 sum = 0;                 find(x,y,1);                 printf("%d\n",sum);             }         }     }     return 0; }