poj3468 A Simple Problem with Integers

模版題

#include 
#include 
#include 
//基於線段樹的區間維護
//維護結點o，它對應區間[L,R]
#define ll long long
const int MAX_N=111111;
const int MAX_Q=111111;
int N,Q;
int A[MAX_N+1];
char T[MAX_Q];
int L[MAX_Q],R[MAX_Q],X[MAX_Q];
ll bit0[MAX_N+1],bit1[MAX_N+1];
ll sum(ll *b,int i)
{
    ll s=0;
    while(i>0){
        s+=b[i];
        i-=i & -i;
    }
    return s;
}
void add(ll* b,int i,int v)
{
    while(i<=N)
    {
        b[i]+=v;
        i+=i&-i;
    }
}
int main()
{
    #ifndef ONLINE_JUDGE
		freopen("D:/1.txt","r",stdin);
		freopen("D:/2.txt","w",stdout);
	#endif
    scanf("%d%d",&N,&Q);
    for(int i=1;i<=N;i++)
    {
        scanf("%d",&A[i]);
    }
    for(int i=1;i<=Q;i++)
    {
        char ch[2];
        scanf("%s",ch);
        if(ch[0]=='Q')
        {
            T[i]=ch[0];
            scanf("%d%d",&L[i],&R[i]);
        }
        else
        {
            T[i]=ch[0];
            scanf("%d%d%d",&L[i],&R[i],&X[i]);
        }
    }
    for(int i=1;i<=N;i++)
    {
        add(bit0,i,A[i]);
    }
    for(int i=1;i<=Q;i++)
    {
        if(T[i]=='C')
        {
            add(bit0,L[i],-X[i]*(L[i]-1));
            add(bit1,L[i],X[i]);
            add(bit0,R[i]+1,X[i]*R[i]);
            add(bit1,R[i]+1,-X[i]);
        }
        else
        {
            ll res=0;
            res+=sum(bit0,R[i])+sum(bit1,R[i])*R[i];
            res-=sum(bit0,L[i]-1)+sum(bit1,L[i]-1)*(L[i]-1);
            printf("%lld\n",res);
        }
    }
}