POJ3468——树状数组支持两个区间操作

推断过程可自己查，得式子：fixsum(x) = (x+1) * ∑(i=1,x)fi - ∑(i=1,x)i*fi;

其中 f 是真实值的修改量，故修改区间变为f的单点修改，求真实值时取f的前缀和加上自己的原值（真实值）。

故修改i*fi时也是普通的单点修改，再普通维护树状数组，每个影响的部分和都加上这个固定值。

最后求前缀和时用fixsum加上原前缀和得到修改后的。

#include<iostream>

#include<cstdio>

using namespace std;

int n,t,L,R,c;

long long a[],f[],fi[],s[];

char ch;

void add(int x,int c)

{

    int y=x;

    for(;x<=n;x+=x&-x)

    {

        f[x]+=c;

        fi[x]+=y*c;

    }

}

long long query(int x)

{

    long long fis=,fs=;

    int y=x;

    for(;x;x-=x&-x)

        fis+=fi[x],fs+=f[x];

    return (y+)*fs-fis;

}

int main()

{

    scanf("%d%d",&n,&t);

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

    {

        scanf("%lld",&a[i]);

        s[i]=s[i-]+a[i];

    }

    while(t--)

    {

        scanf(" %c",&ch);

        if(ch=='C')

        {

            scanf("%d%d%d",&L,&R,&c);

            add(L,c);add(R+,-c);

        }

        else

        {

            scanf("%d%d",&L,&R);

            printf("%lld\n",(query(R)+s[R])-(query(L-)+s[L-]));

        }

    }

    return ;

}

巴特西

POJ3468——树状数组支持两个区间操作

最新文章

热门文章