nyoj-116-士兵杀敌（二）

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
int tree[1000010],n,m,i;
int main()
{
    void add(int left,int num);
    int getsum(int end);
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int a,b1,b2;
        char ch[10];
        memset(tree,0,sizeof(tree));
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a);
            add(i,a);
        }
        for(i=0;i<m;i++)
        {
            scanf("%s%d%d",ch,&b1,&b2);
            if(ch[0]=='A')
                add(b1,b2);
            else
                printf("%d
",getsum(b2)-getsum(b1-1));
        }
    }
    return 0;
}
int lowbit(int n)
{
    return n&(-n);
}
void add(int left,int num)
{
    while(left<=n)
    {
        tree[left]+=num;
        left+=lowbit(left);
    }
}
int getsum(int end)
{
    int sum=0;
    while(end>0)
    {
        sum+=tree[end];
        end-=lowbit(end);
    }
    return sum;
}