题目大意：

反正都是中文的，可以自己去读。把题目的意思抽象化就是，给你一串数（50000）个，然后进行最多40000次操作，操作内容包括：改变某一个数的值，查询该数组的一个连续区间 [l,r] 的所有值的和。

分析：

如果用普遍的方法，那么，每次改变某一个数的值时间复杂度O（1）；查询一次，时间复杂度O(n)；如果查询太多，肯定就超时了。解决办法就是引入树状数组，让查询区间和和改变某一数的值的时间复杂度都变为O(logn)；这样就不会超时了。

代码：

#include<iostream>
#include<stdio.h>
#include<string.h>

using namespace std;

int a[50050]={0};
int tree[50050]={0};
int n;

int lowbit(int x)//tree[x]为a[x]~a[x-lowbit(x)+1]的和。
{
    return (-x)&x;
}

void add(int i,int y)//给a[i]增加y 
{
    a[i]+=y;
    while(i<=n)
    {
        tree[i]+=y;
        i+=lowbit(i);
    }
}

int f(int x)//计算[1,x]的值 
{
    int s=0;
    while(x>=1)
    {
        s=s+tree[x];
        x=x-lowbit(x);
    }
    return s;
}

int sum(int l,int r)//计算[l,r]的值 
{
    return f(r)-f(l)+a[l];
}


int main()
{   
    int tt;
    cin>>tt;
    for(int test=1;test<=tt;test++)
    {
        memset(tree,0,sizeof(tree));
        memset(a,0,sizeof(a));
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            int ll;
            scanf("%d",&ll);
            add(i,ll);
        }
        char l[20]={0};
        int a,b;
        cout<<"Case "<<test<<":"<<endl;
        while(scanf("%s",l))
        {
            if(l[0]=='E')break;
            scanf("%d%d",&a,&b);
            if(l[0]=='Q')
            {
                cout<<sum(a,b)<<endl;
            }
            if(l[0]=='A')
            {
                add(a,b);
            }
            if(l[0]=='S')
            {
                add(a,-b);
            }
        }
    }
}

后注：

这道题卡时间卡的比较严重，cin变成scanf就从超时变成了ac。不过也可能是因为我代码效率不高的原因。在想树状数组的时候，感觉一开始把已知的a数组创建成tree的过程还可以更快，虽然时间复杂度也是O(logn)，但是总的操作次数确实会变少，有时间要想一下这个思路的代码实现，然后在下一篇博客或者下次培训的时候把bulid函数思路讲出来吧。