pku3468 A Simple Problem with Integers

 

#include<stdio.h>

const int MAX=100005;
int base[MAX];
struct Node
{
    long long value;
    long long delta;
};
Node tree[MAX*3];

long long build(int node,int l,int r)
{
    tree[node].delta=0;
    if(l==r) return tree[node].value=base[l];
    
    int mid=(l+r)>>1;
    tree[node].value=build(node<<1,l,mid)+build((node<<1)+1,mid+1,r);
    return tree[node].value;
}

void update(int node,int l,int r,int lc,int rc,long long newDelta)    //自上而下的更新

{
    tree[node].value+=(rc-lc+1)*newDelta;    //更新目标结点及其父结点的基值

    if(l==lc&&r==rc)
    {
        tree[node].delta+=newDelta;    //更新增量是为了提供其子结点使用，而不是为该结点自身使用

        return;
    }

    int mid=(l+r)>>1;
    if(mid<lc) update((node<<1)+1,mid+1,r,lc,rc,newDelta);
    else if(mid>=rc) update(node<<1,l,mid,lc,rc,newDelta);
    else
    {
        update(node<<1,l,mid,lc,mid,newDelta);
        update((node<<1)+1,mid+1,r,mid+1,rc,newDelta);
    }
}

void inquire(int node,int l,int r,int lc,int rc,long long &sum)
{
    if(l==lc&&r==rc)
    {
        sum+=tree[node].value;            //目标结点提供基值

        return;
    }

    sum+=tree[node].delta*(rc-lc+1);    //所有目标结点的父结点提供增量，目标结点的基值已发生更新                                    


    int mid=(l+r)>>1;
    if(mid<lc) inquire((node<<1)+1,mid+1,r,lc,rc,sum);
    else if(mid>=rc) inquire(node<<1,l,mid,lc,rc,sum);
    else
    {
        inquire(node<<1,l,mid,lc,mid,sum);
        inquire((node<<1)+1,mid+1,r,mid+1,rc,sum);
    }
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++) scanf("%d",&base[i]);
    build(1,1,n);

    int b1,b2;
    char str[2];
    for(int i=0;i<m;i++)
    {
        scanf("%s",str);

        if(str[0]=='Q')
        {
            scanf("%d%d",&b1,&b2);
            long long sum=0;
            inquire(1,1,n,b1,b2,sum);
            printf("%lld\n",sum);    //和=基值+增量

        }
        else
        {
            long long delta;
            scanf("%d%d%lld",&b1,&b2,&delta);
            update(1,1,n,b1,b2,delta);
        }
    }
    return 0;
}

总结：

将数位的基值和增量分开存贮，更新线段树时主要是更新增量，查询线段树时重新组装基值和增量。