解题报告 P4868 Preprefix sum

题目内容

P4868

大意：维护一串序列，支持单点修改和前前缀和查询（\displaystyle\sum_{k=1}^i\sum_{j=1}^ka_j）

解题思路

前前缀和，就是前缀和的前缀和，既然需要查询前前缀和，那么就可以想到维护序列的前缀和，查询的时候区间查询 [1,i]，修改的时候由于修改一个特定位置的数，后面的所有前缀和都会被影响，所以相当于区间修改前缀和，区间修改区间查询，很容易想到使用线段树维护。

当然用差分处理了的树状数组也可以，但是线段树明显好写理解。

要注意的细节：

• 建线段树的时候记得是记录前缀和
• 修改 a_i 为 x 的时候相当于 (i,n] 的前缀和都要加上 x-a_i，所以 a_i 一定要存下来

代码：

#include <cstdio>
#include <cctype>
#define L (k<<1)
#define R (L|1)
#define M ((i+j)>>1)
typedef long long ll;

const int maxn=100005;
ll a[maxn],s[maxn],f[maxn<<2],tag[maxn<<2];

int n,m;

inline ll read()
{
    char c = getchar();
    ll s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

void build(int i,int j,int k)
{
    if(i==j)
    {
        a[i]=read();
        s[i]=s[i-1]+a[i];
        f[k]=s[i];
        return;
    }
    build(i,M,L);
    build(M+1,j,R);
    f[k]=f[L]+f[R];
    return;
}

inline void down(int i,int j,int k)
{
    f[L]+=tag[k]*(M-i+1ll);
    f[R]+=tag[k]*(ll)(j-M);
    tag[L]+=tag[k];
    tag[R]+=tag[k];
    tag[k]=0;
    return;
}

void modify(int i,int j,int l,int r,int k,int d)
{
    if(i>=l && j<=r)
    {
        f[k]+=d*(j-i+1ll);
        tag[k]+=d;
        return;
    }
    if(tag[k])
        down(i,j,k);
    if(l<=M)
        modify(i,M,l,r,L,d);
    if(r>M)
        modify(M+1,j,l,r,R,d);
    f[k]=f[L]+f[R];
    return;
}

ll ask(int i,int j,int l,int r,int k)
{
    if(i>=l && j<=r)
        return f[k];
    if(tag[k])
        down(i,j,k);
    ll ans=0;
    if(l<=M)
        ans+=ask(i,M,l,r,L);
    if(r>M)
        ans+=ask(M+1,j,l,r,R);
    return ans;
}

int main()
{
    n=read(),m=read();
    build(1,n,1);
    char opt[10];
    int i;
    while(m--)
    {
        scanf("%s %d",opt,&i);
        if(opt[0]=='M')
        {
            ll x=read();
            modify(1,n,i,n,1,x-a[i]);
            a[i]=x;
        }
        else
            printf("%lld\n",ask(1,n,1,i,1));
    }
    return 0;
}