POJ-3468:A Simple Problem with Integers（区间更新）

线段树

Description

给出了一个序列，你需要处理如下两种询问。

"C a b c"表示给[a, b]区间中的值全部增加c (-10000 ≤ c ≤ 10000)。

"Q a b" 询问[a, b]区间中所有值的和。

Input

第一行包含两个整数N, Q。1 ≤ N,Q ≤ 100000.

第二行包含n个整数，表示初始的序列$A (-1000000000 ≤ A_i ≤ 1000000000)$。

接下来Q行询问，格式如题目描述。

Output
对于每一个Q开头的询问，你需要输出相应的答案，每个答案一行。

Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

Sample Output

4
55
9
15

要更新某区间内的值，如果单点更新，操作次数就可能会很多，很有可能超时，因此引入了延迟标记（lazy）这个概念。每次不必访问到根节点，只需要到更新的区间所在的节点就可以。例如增加了某区间的每个值后，求当前区间的最大值，即用区间长度乘以当前lazy标记即可，减少了操作的次数，提高了效率。

• 创建：在结构体中加入lazy标记，建树的时候将它初始化为0或者-1（初始化为0可能会好一点，因为有可能对区间所有的值同时减去某个数）。

void build(int id,int l,int r)
{
    s[id].l=l;
    s[id].r=r;
    s[id].lazy=0;
    if(l==r)
        s[id].sum=a[l];
    else
    {
        int mid=(l+r)/2;
        build(id*2,l,mid);
        build(id*2+1,mid+1,r);
        s[id].sum=s[id*2].sum+s[id*2+1].sum;
    }
}

• 更新区间和标记的传递：lazy标记用来记录当前节点是否需要进行某种修改，当我们所需要操作的区间完全覆盖了当前区间，那么更改当前节点的lazy标记，暂时不用更新子节点。如果并未完全覆盖该节点，并且该节点上已经存在lazy标记，那么按照标记修改它的子节点对应信息并且给子节点修改lazy标记，并将自己的标记清除。

void pushdown(int id)
{
    s[id*2].lazy+=s[id].lazy;
    s[id*2+1].lazy+=s[id].lazy;
    s[id*2].sum+=s[id].lazy*(s[id*2].r-s[id*2].l+1); //区间长度乘以当前lazy标记
    s[id*2+1].sum+=s[id].lazy*(s[id*2+1].r-s[id*2+1].l+1);
    s[id].lazy=0; //标记向下传递后清空
}
void rep(int id,int l,int r,int val)
{
    if(l<=s[id].l&&s[id].r<=r)
    {
        s[id].lazy+=val; //可能多次被标记而没有向下传递
        s[id].sum+=val*(s[id].r-s[id].l+1);
        return; //需要更新的区间完全包含了该区间，标记该区间
    }
    if(s[id].lazy!=0) //若不是完全包含，并且这个区间有标记，标记向下传递
        pushdown(id);
    int mid=(s[id].l+s[id].r)/2;
    if(r<=mid)
        rep(id*2,l,r,val);
    else if(l>mid)
        rep(id*2+1,l,r,val);
    else
    {
        rep(id*2,l,r,val);
        rep(id*2+1,l,r,val);
    }
    s[id].sum=s[id*2].sum+s[id*2+1].sum;  //根据左右子树更新当前节点的和，相当于pushup
}

• 求区间和：

long long sum(int id,int l,int r)
{
    if(l<=s[id].l&&s[id].r<=r)
        return s[id].sum;
    if(s[id].lazy!=0)
        pushdown(id);
    int mid=(s[id].l+s[id].r)/2;
    if(r<=mid)
        return sum(id*2,l,r);
    else if(l>mid)
        return sum(id*2+1,l,r);
    else
        return sum(id*2,l,r)+sum(id*2+1,l,r);
}

• 完整代码：

#include<stdio.h>
int n;
long long a[100005];
struct node
{
    int l,r;
    long long sum,lazy;
}s[100005*4];
void build(int id,int l,int r)
{
    s[id].l=l;
    s[id].r=r;
    s[id].lazy=0;
    if(l==r)
        s[id].sum=a[l];
    else
    {
        int mid=(l+r)/2;
        build(id*2,l,mid);
        build(id*2+1,mid+1,r);
        s[id].sum=s[id*2].sum+s[id*2+1].sum;
    }
}
void pushdown(int id)
{
    s[id*2].lazy+=s[id].lazy;
    s[id*2+1].lazy+=s[id].lazy;
    s[id*2].sum+=s[id].lazy*(s[id*2].r-s[id*2].l+1);
    s[id*2+1].sum+=s[id].lazy*(s[id*2+1].r-s[id*2+1].l+1);
    s[id].lazy=0;
}
void rep(int id,int l,int r,int val)
{
    if(l<=s[id].l&&s[id].r<=r)
    {
        s[id].lazy+=val;
        s[id].sum+=val*(s[id].r-s[id].l+1);
        return; //需要更新的区间完全包含了该区间，标记该区间
    }
    if(s[id].lazy!=0) //若不是完全包含，并且这个区间有标记，标记向下传递
        pushdown(id);
    int mid=(s[id].l+s[id].r)/2;
    if(r<=mid)
        rep(id*2,l,r,val);
    else if(l>mid)
        rep(id*2+1,l,r,val);
    else
    {
        rep(id*2,l,r,val);
        rep(id*2+1,l,r,val);
    }
    s[id].sum=s[id*2].sum+s[id*2+1].sum;
}
long long sum(int id,int l,int r)
{
    if(l<=s[id].l&&s[id].r<=r)
        return s[id].sum;
    if(s[id].lazy!=0)
        pushdown(id);
    int mid=(s[id].l+s[id].r)/2;
    if(r<=mid)
        return sum(id*2,l,r);
    else if(l>mid)
        return sum(id*2+1,l,r);
    else
        return sum(id*2,l,r)+sum(id*2+1,l,r);
}
int main()
{
    int q,i,x,y,v;
    char ch[3];
    while(scanf("%d%d",&n,&q)!=EOF)
    {
        for(i=1;i<=n;i++)
            scanf("%lld",&a[i]);
        build(1,1,n);
        while(q--)
        {
            scanf("%s",ch);
            if(ch[0]=='Q')
            {
                scanf("%d%d",&x,&y);
                printf("%lld\n",sum(1,x,y));
            }
            if(ch[0]=='C')
            {
                scanf("%d%d%d",&x,&y,&v);
                rep(1,x,y,v);
            }
        }
    }
    return 0;
}