AcWing 243. 一个简单的整数问题2

给定一个长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：

1、“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。

2、“Q l r”，表示询问 数列中第 l~r 个数的和。

对于每个询问，输出一个整数表示答案。

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int N=1e5+5;

int n,m,a[N],b[N],tr[N];

char op[2];

int lowbit(int x)

{

    return x&-x;

}

void add(int b[],int x,int c)

{

    for(int i=x;i<=n;i+=lowbit(i))

    b[i]+=c;

}

int sum(int b[],int x)

{

    int res=0;

    for(int i=x;i;i-=lowbit(i))

    res+=b[i];

    return res;

}

int Rsum(int x){return (x+1)*sum(b,x)-sum(tr,x);}

signed main()

{

    int l,r,d;

    cin>>n>>m;

    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);

    for(int i=1;i<=n;i++)

    {

        add(b,i,a[i]-a[i-1]);

        add(tr,i,i*(a[i]-a[i-1]));

    }

    for(int i=1;i<=m;i++)

    {

        scanf("%s",op);

        if(op[0]=='C')

        {

            scanf("%lld%lld%lld",&l,&r,&d);

            add(b,l,d);add(b,r+1,-d);

            add(tr,l,l*d);add(tr,r+1,-(r+1)*d);

        }

        else

        {

            scanf("%lld%lld",&l,&r);

            printf("%lld\n",Rsum(r)-Rsum(l-1));

        }

    }

    return 0;

}

AcWing 243. 一个简单的整数问题2的相关教程结束。