树状数组.cpp

acm 常用算法和代码库

#include <iostream>
using namespace std;

__int64 a[1000001]={0};
__int64 c[1000001]={0};
__int64 n;
__int64 lowbit(__int64 x)
{
    int res;
    res=x & (x^(x-1));
    return res;
}
void change(__int64 k,__int64 delta)
{
    a[k]+=delta;
    while(k<=n)
    {
       c[k]=c[k]+delta;
       k=k+lowbit(k);
       
    }
}

__int64 request(__int64 end){ 
     __int64 sum=0; 
     while (end>0) { 
        sum+=c[end]; 
        end-=lowbit(end); 
    } 
    return sum; 
}

int main()
{
    
    char cmd;
    __int64 req;
    while(scanf("%I64d%I64d",&n,&req)!=EOF)
    {
        __int64 i,j,s,e,delta;
        memset(a,0,sizeof(a));
        memset(c,0,sizeof(c));
        for(i=1;i<=n;i++)
           scanf("%I64d",&a[i]);
        getchar();
        for(j=1;j<=n;j++)
        {
            change(j,a[j]);
        } 
        while(req--)
        {
           scanf("%c%I64d%I64d",&cmd,&s,&e);
           getchar();
           switch(cmd)
           {
                      case 'C':
                               scanf("%I64d",&delta);//cin>>s>>e>>delta;
                               for(j=s;j<=e;j++)
                                   change(j,delta);
                               getchar();          
                               break;
                      case 'Q':
                               cout<<request(e)-request(s-1)<<endl;
                               break;
                               
           }
        }
    }
}