【数据结构】线段树3

线段树区间修改,延迟标记

在区间查询中,每次询问区间$[l,r]$完全覆盖当前结点时,就可以直接返回当前答案。不过在区间修改中,如果当前结点被询问区间$[l,r]$完全覆盖,那么以该结点为子树的整棵树都会修改,如果逐一进行修改,那么一次修改就会达到$O(N)$的复杂度,似乎无法接受。
而且虽然我们修改了整棵子树,但是以后的查询指令却完全不需要区间$[l,r]$的子区间,所以我们似乎做了无用功。
于是我们在修改操作中,同样可以当$l\leq p_{l} \leq p_{r}\leq r$时立即返回,只不过在回溯前向$p$增加一个标记,标记“该结点曾经被修改过,但其子结点尚未更新”。
在后续的操作中,需要从结点$p$向下递归,再检查$p$是否具有标记。

【题解】POJ 3468

#include<cstdio>

typedef long long int64;

const int MAXN = 100000 + 6;

int a[MAXN];

class SegmentTree{
    public:int l,r;
    public:int64 sum,add;
};
SegmentTree t[MAXN * 4];

inline int LEFT(int x){return x << 1;}
inline int RIGHT(int x){return x << 1 | 1;}
inline int MID(int l,int r){return (l + r) >> 1;}

void build(int p,int l,int r){
    t[p].l = l;t[p].r = r;
    if(l == r){
        t[p].sum = a[l];
        return;
    }
    build(LEFT(p),l,MID(l,r));
    build(RIGHT(p),MID(l,r) + 1,r);
    t[p].sum = t[LEFT(p)].sum + t[RIGHT(p)].sum;
}

void spread(int p){
    if(t[p].add){
        t[LEFT(p)].sum += (t[p].add * (t[LEFT(p)].r - t[LEFT(p)].l + 1));
        t[RIGHT(p)].sum += (t[p].add * (t[RIGHT(p)].r - t[RIGHT(p)].l + 1));
        t[LEFT(p)].add += t[p].add;
        t[RIGHT(p)].add += t[p].add;
        t[p].add = 0;
    }
}

void change(int p,int l,int r,int d){
    if(l <= t[p].l && r >= t[p].r){
        t[p].sum += ((int64)d * (t[p].r - t[p].l + 1));
        t[p].add += d;
        return;
    }
    spread(p);
    if(l <= MID(t[p].l,t[p].r)){
        change(LEFT(p),l,r,d);
    }
    if(r > MID(t[p].l,t[p].r)){
        change(RIGHT(p),l,r,d);
    }
    t[p].sum = t[LEFT(p)].sum + t[RIGHT(p)].sum;
}

int64 ask(int p,int l,int r){
    if(l <= t[p].l && r >= t[p].r){
        return t[p].sum;
    }
    spread(p);
    int64 ans = 0;
    if(l <= MID(t[p].l,t[p].r)){
        ans += ask(LEFT(p),l,r);
    }
    if(r > MID(t[p].l,t[p].r)){
        ans += ask(RIGHT(p),l,r);
    }
    return ans;
}

int main(){
    int n,m;
    scanf("%d %d\n",&n,&m);
    
    for(int i = 1;i <= n;i++){
        scanf("%d\n",&a[i]);
    }
    build(1,1,n);
    while(m--){
        char op;
        int x,y,k;
        scanf("%c",&op);
        if(op == 'C'){
            scanf("%d %d %d\n",&x,&y,&k);
            change(1,x,y,k);
        }else{
            scanf("%d %d\n",&x,&y);
            printf("%lld\n",ask(1,x,y));
        }
    }
    
    return 0;
}