D

Description

Lily 特别喜欢养花，但是由于她的花特别多，所以照料这些花就变得不太容易。她把她的花依次排成一行，每盆花都有一个美观值。如果Lily把某盆花照料的好的话，这盆花的美观值就会上升，如果照料的不好的话，这盆花的美观值就会下降。有时，Lily想知道某段连续的花的美观值之和是多少，但是，Lily的算术不是很好，你能快速地告诉她结果吗？

Input

	第一行一个整数T，表示有T组测试数据。
每组测试数据的第一行为一个正整数N(N<=50000)，表示Lily有N盆花。接下来有N个正整数，第i个正整数ai表示第i盆花的初始美观值(1<=ai<=50)。
接下来每行有一条命令，命令有4种形式：
（1）Add i j, i和j为正整数，表示第i盆花被照料的好，美观值增加j(j<=30)
（2）Sub i j, i和j为正整数，表示第i盆花被照料的不好，美观值减少j(j<=30)
（3）Query i j, i和j为正整数，i<=j，表示询问第i盆花到第j盆花的美观值之和
（4）End，表示结束，这条命令在每组数据最后出现
每组数据的命令不超过40000条

Output

	对于第i组数据，首先输出"Case i:"和回车。
对于每个"Query i j"命令，输出第i盆花到第j盆花的美观值之和。

Sample Input

1

9
7 9 8 4 4 5 4 2 7
Query 7 9
Add 4 9
Query 3 6
Sub 9 6
Sub 3 3
Query 1 9
End

Sample Output

Case 1:

13
30
50

 

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
static int a[50002],b[50002],N;
int lowbit(int t)
{
    return t&(-t);
}
void upDate(int x,int num)//更新树状数组
{
  while(x<=N)
  {
      b[x]+=num;
      x+=lowbit(x);
  }
}
int getSum(int x)//求和
{
    int s=0;
    while(x>0)
    {
        s+=b[x];
        x-=lowbit(x);
    }
    return s;
}

int main()
{
    int n,num;
    char str[10];
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        cout<<"Case "<<i+1<<':'<<endl;
        scanf("%d",&num);N=num;
     memset(b,0,sizeof(b));
       for(int i=1;i<=num;i++)
       {
           scanf("%d",&a[i]);
           upDate(i,a[i]);
       }
    while(scanf("%s",str))
    {
            if(str[0]=='E')  break;
    int i,j;
    scanf("%d%d",&i,&j);
    switch(str[0])
    {
        case 'A':upDate(i,j);break;
        case'S':upDate(i,-j);break;
        case'Q':cout<<getSum(j)-getSum(i-1)<<endl;break;
    }
}
    }
    return 0;
}

 分析：本题既可以用线段树解决也可以用树状数组解决新，一开始我是用switch做的，但后来发现超时，于是又用树状数组做一遍，线段树有模板函数，只需要自己改一些判断题条件久可以了。

  心得：像这种大数据的题目如果用一般的方法来做很可能超时，所以我们就要学习一些特殊的解题方法。线段树一般使用与点的更新，求和，区间的删减