莫欺少年穷，修魔之旅在这开始—>算法提高课题解

树状数组思路：

1. 预处理tr1和tr2的前缀和
2. tr1：维护 b[i] 的前缀和；tr2：维护 i * b[i] 的前缀和
3. sum(tr1, x) = b[1 ~ x]；sum(tr2, x) = b[1] + 2 * b[2] + …… + x * b[x]
4. a[1 ~ x] = sum(tr1, x) * (x + 1) - sum(tr2, x)

可参考： 线段树方法

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 100010;

int n,m;
int a[N]; // b[i] = a[i] - a[i-1]
LL tr1[N]; //维护 b[i] 的前缀和
LL tr2[N]; //维护 i * b[i] 的前缀和

int lowbit(int x)
{
    return x&-x;
}

void add(LL tr[],int x,LL c)
{
    for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
}

// sum(tr1, x) = b[1 ~ x], sum(tr2, x) = b[1] + 2 * b[2] + …… + x * b[x]
LL sum(LL tr[],int x)
{
    LL res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}

// a[1 ~ x] = (b[1] + b[2] + …… + b[x]) * (x + 1) - (b[1] + 2 * b[2] + …… + x * b[x])
LL prefix_sum(int x)
{
    return sum(tr1,x)*(x+1)-sum(tr2,x);
}

int main()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++)
    {
        cin>>a[i];

        //预处理 tr1 和 tr2
        add(tr1,i,a[i]-a[i-1]);
        add(tr2,i,(LL)i*(a[i]-a[i-1]));
    }

    while(m--)
    {
        char op;
        int l,r,d;
        cin>>op;

        //表示把 A[l],A[l+1],…,A[r] 都加上 d
        if(op=='C')
        {
            cin>>l>>r>>d;
            add(tr1,l,d),add(tr1,r+1,-d);
            add(tr2,l,l*d),add(tr2,r+1,(r+1)*-d);
        }
        //表示询问数列中第 l∼r 个数的和
        else 
        {
            cin>>l>>r;
            cout<<prefix_sum(r)-prefix_sum(l-1)<<endl;
        }
    }

    return 0;
}