1 /* 2 树状数组（二叉索引树，Binary Indexed Tree，BIT） 3  4          5 */ 6  7 #include 
      
        8 #include 
       
         9 using namespace std;10 11 const int maxn = 50010;12 int sum[maxn];13 int a[maxn];14 int n ;15 16 int lowbit (int x)    //取x的最低位1，比如4，则返回4，如5，则返回117 {18     return x & (-x) ;19 }20 21 void add(int i,int value)    //将第i个元素增加value22 {23     //i的祖先都要增加val24     while(i<=n)25     {26         sum[i] += value ;27         i += lowbit(i) ;    //将i的最低位1补1，得到其祖先28 29     }30 }31 int Sum(int i)    //求前i项和32 {33     int count = 0;34     //将前i项分段35     while(i>0)36     {37         count += sum[i] ;38         i -= lowbit(i) ;    //去掉i的最低位139     }40     return count ;41 }42 43 void main()44 {45     int t ;46     cin>>t ;47     for(int cnt = 1;cnt<=t;cnt++)48     {49         memset(sum,0,sizeof(sum));50         cout<<"Case "<
        
         <<":"<
         
          >n ;52         for(int i=1;i<=n;i++)    //注意数组从1开始的53         {54             scanf("%d",&a[i]);55             add(i,a[i]) ;56         }57         string s;58         while(cin>>s , s !="End")59         {60             int i,j;61             scanf("%d%d",&i,&j);62             if(s=="Query")63             {64                 printf("%d\n",Sum(j)-Sum(i-1));65             }66             if(s=="Add")67             {68                 add(i,j) ;69             }70             if(s=="Sub")71             {72                 add(i,-j);73             }74         }75     }76 }