题目描述

对于i*b[i]的前缀和问题给出了注释解释。

这里b[i]是维护前缀和。

算法1

C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;

typedef long long LL;

const int N=1e5+10;
LL tr1[N];
LL tr2[N];
LL a[N];
int n,m;

/*
yxc解释：
tr2维护的是i * b[i]的前缀和，而b[i] = a[i] - a[i - 1]，所以
当我们给a[L] ~ a[R]加上d时，对i * b[i]的影响只有两处：L * b[L]，
此时由于b[L]增加了d，所以L * b[L]就应该增加L * d；
同理(R + 1) * b[R + 1]由于b[R + 1]减少了d，所以它应该减去(R + 1) * d。

lyd大佬的书中维护的是改变量，还没理解他的做法中为什么能维护i*b[i](1->x)；
*/

LL ask(LL tr[],int x)
{
    LL ans=0;
    for(;x;x-=(x&-x)) ans+=tr[x];
    return ans;
}

void add(LL tr[],int x,LL y)
{
    for(; x<=n; x+=(x& -x) ) tr[x]+=y;
}

LL ask_sum(int x)
{
    return ask(tr1,x)*(x+1)-ask(tr2,x);
}

int main()
{

    cin>>n>>m;

    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    for (int i = 1; i <= n; i ++ )
    {
        int b = a[i] - a[i - 1];
        add(tr1, i, b);
        add(tr2, i, (LL)b * i);
    }

    char op[5];
    int x,y,z;
    for(int i=1;i<=m;i++)
    {
        scanf("%s",op);

        if(op[0]=='C')
        {
            scanf("%d %d %d",&x,&y,&z);

            add(tr1,x,z),add(tr2,x,x*z);
            add(tr1,y+1,-z),add(tr2,y+1,(y+1)*(-z));
        }
        else
        {
            scanf("%d %d",&x,&y);
            cout<<ask_sum(y)-ask_sum(x-1)<<endl;;
        }

    }
    return 0;
}