线段树(Segment Tree)+懒标记(Lazy Tag)总结

/ 0评 /

线段树是非常基础的算法了……

线段树是一种二叉树,可视为树状数组的变种,最早出现在2001年,由程序竞赛选手发明。我们ZS老师说过:“所有可以用树状数组解决的题目都可以用线段树解决,但是部分线段数可以解决的题目却无法用树状数组解决。”由此可见线段树十分强大……

此资料结构实际应用用途不大,但由于其程式易于实作而被广泛应用于程式竞赛当中。其用途是在O(\log N)查询一个指定区间内的资讯,并可在同样的时间复杂度支援更新等操作。
——维基百科

例题

先来看看洛谷上的线段树模版题:【模板】线段树 1

题目描述

如题,已知一个数列,你需要进行下面两种操作:
1.将某区间每一个数加上x
2.求出某区间每一个数的和

输入输出格式

输入格式:
第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3或4个整数,表示一个操作,具体如下:
操作1: 格式:1 x y k 含义:将区间[x,y]内每个数加上k
操作2: 格式:2 x y 含义:输出区间[x,y]内每个数的和

输出格式:
输出包含若干行整数,即为所有操作2的结果。

输入输出样例

输入样例

5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4

输出样例

11
8
20

说明

时空限制:1000ms,128M
数据规模:
对于30%的数据:N<=8,M<=10
对于70%的数据:N<=1000,M<=10000
对于100%的数据:N<=100000,M<=100000
(数据已经过加强^_^,保证在int64/long long数据范围内)
样例说明:
样例说明

线段树的定义和构造

线段树(Segment Tree)是一个平衡的二叉树,所有叶子到根的距离最多只差1。令整个区间的长度为N,则其有N个叶节点,每个叶节点代表一个单位区间,每个内部结点代表的区间为其两个儿子代表区间的联集。

翻译成人话就是:线段树是个二叉树,每个节点表示一个区间(或许应该叫区间树……),叶节点代表的区间大小是1(即单位区间)。(以上面的例题为例)很容易理解,根据叶节点我们可以向上累计,对于每个非叶节点,很容易构造出其代表的区间内所有数字加和(以下称为“管辖区间和”(我自己起的名字……因为我觉得“管辖”这个词很高端……),用tree[x]表示x节点管辖区间和)(即每个点左右儿子代表区间和的加和)。这样向上构造,我们就可以造出一颗线段树。这就是build函数构造线段树的过程:

inline void build(int p,int tl,int tr){
    tag[p]=0;
    if (tl==tr) {tree[p]=a[tl];return;}
    int mid=((tr-tl)>>1)+tl;
    build((p<<1)  ,tl,mid  );
    build((p<<1)+1,mid+1,tr);
    tree[p]=tree[p<<1]+tree[(p<<1)+1];
}

区间更新与懒标记

如果没有区间更新,我们就用不到懒标记了,因为对于单点更新,直接向上推,O(\log_2 N)的时间内就可以得出结果。但是区间更新就十分麻烦:如果一个个单点进行更新,最高需要O(N* \log_2 N)!显然很容易超时。懒标记(Lazy Tag)其实是对朴素的线段树的一个优化,可以让区间更新也达到O(\log_2 N)级别。所以首先我们来认识一下懒标记:

懒标记

懒标记(Lazy Tag),也有的地方翻译成“延迟标记”(听起来高端……),就是指在更新一部分区间的时候,不更新这个区间里面的每个点,而是(懒惰地)把这个区间分割成很多个能用线段树上的点表示的区间(当然是分的区间越少越好,也就是说每个区间越大越好),只修正代表这个区间的点,再把这些区间标记下,下次如果要查询的区间与这个区间有交集并且没有包含这个区间,就说明需要“分割”这个区间,再将这个区间向下修正。这样时间复杂度就可以优化很多。

如何进行区间更新

刚才已经提到,如果要把区间[L,R]中所有元素加上delta,则只需要从线段树的根节点开始向下寻找,找到第一个被[L,R]包含的区间,就修正这个区间(注意“修正这个区间”只是增加这个区间和的标记和懒标记,不是把这个区间向下修正),然后继续向下找,直到找出来的一段段区间把[L,R]都覆盖了。

区间查询

区间查询和区间更新有点类似,假设要查询[L,R],同样从根节点开始乡向下“分割”,不同之处在于:可能需要将刚才的懒标记用于向下修正。(具体见代码~)

完整代码(注释版)

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=2000005;
int n,m;
long long a[maxn],tree[maxn],tag[maxn];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
inline long long llread(){
    long long ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=(long long)-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*(long long)10+(long long)(ch-'0'),ch=getchar();
    return (long long)ret*f;
}
inline void build(int p,int tl,int tr){  //构造Segment Tree 
    tag[p]=0;
    if (tl==tr) {tree[p]=a[tl];return;}
    int mid=((tr-tl)>>1)+tl;
    build((p<<1)  ,tl,mid  );
    build((p<<1)+1,mid+1,tr);
    tree[p]=tree[p<<1]+tree[(p<<1)+1];
}
inline void push_down(int tl,int tr,int p){  //push_down函数负责向下传递,将存储的tag数组用于修正 
    int mid=((tr-tl)>>1)+tl;
    tree[p<<1]+=(long long)tag[p]*(mid-tl+1);  //只需要修正一对左右儿子,不需要一直传递到叶节点 
    tag[p<<1]+=tag[p];  //因为没有往下修正,所以要把儿子的tag累计上 
    tree[(p<<1)+1]+=(long long)tag[p]*(tr-mid);
    tag[(p<<1)+1]+=tag[p];
    tag[p]=0;
}
inline void update(int sl,int sr,int tl,int tr,long long delta,int p){
    if (sl<=tl&&sr>=tr){  //p管辖的区间在修改范围内 
        tree[p]+=delta*(long long)(tr-tl+1);
        tag[p]+=delta;  //tag数组记录剩下的未向下传递的,实现“lazy tag”
        return;
    }
    push_down(tl,tr,p);  //如果没有完全包含p管辖的区间,则说明应该向下“分割”,所以应该用tag数组先修正下面的tree[] 
    int mid=((tr-tl)>>1)+tl;  //分割[tl,tr]区间 
    if (sl<=mid) update(sl,sr,tl,mid,delta,p<<1);
    if (mid<sr)  update(sl,sr,mid+1,tr,delta,(p<<1)+1);
    tree[p]=tree[p<<1]+tree[(p<<1)+1];  //向上累计 
}
inline long long query(int sl,int sr,int tl,int tr,int p){  //查询操作 
    if (sl<=tl&&sr>=tr) return tree[p];  //如果完全包含p所管辖的区间则直接返回tree[p] 
    long long ret=0;  //否则就“分割” 
    push_down(tl,tr,p);  //先要把当前的tag用于修正下面两个儿子,这样才能保证下面query用到的tree[]是正确的 
    int mid=((tr-tl)>>1)+tl;
    if (sl<=mid) ret+=(long long)query(sl,sr,tl,mid,p<<1);
    if (mid<sr)  ret+=(long long)query(sl,sr,mid+1,tr,(p<<1)+1);
    return ret;
}
int main(){
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    n=read();m=read();
    for (int i=1;i<=n;i++) a[i]=llread();
    build(1,1,n);
    for (int i=1;i<=m;i++){
        int c=read();
        if (c==1){
            int x=read(),y=read();
            long long z=llread();
            update(x,y,1,n,z,1);
        } else
        if (c==2){
            int x=read(),y=read();
            printf("%lld\n",query(x,y,1,n,1));
        }
    }
    return 0;
}

参考

https://www.luogu.org/blog/pks-LOVING/senior-data-structure-qian-tan-xian-duan-shu-segment-tree
https://baike.baidu.com/item/%E7%BA%BF%E6%AE%B5%E6%A0%91/10983506
https://zh.wikipedia.org/zh/%E7%B7%9A%E6%AE%B5%E6%A8%B9_(%E5%84%B2%E5%AD%98%E5%8D%80%E9%96%93)


知识共享许可协议 本文章采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
欢迎转载,如有错误欢迎指出。
本文链接:https://skywt.cn/posts/segment-tree/


发表评论

电子邮件地址不会被公开。 必填项已用*标注