数据结构之王——线段树详解

· · 算法·理论

引子

前言

线段树作为我的名字一个非常好用的数据结构，属于提高组必备知识点，这个文章将对线段树入门用法进行详细的介绍。

从倍增到线段树

我们都知道倍增常被用来进行静态区间查询，在查询最值的时候可以做到 O(1) 查询，同时在查询区间和的时候可以用这种方式进行查询：

int a[N][logN],Log[N];//a为倍增数组，Log为预处理对数
int query(int l,int r){
    int res=0;
    for(int i=Log[r-l+1];i>=0;i--){
        if(r-l+1>=(1<<i)){
            res+=a[l][i];
            l+=1<<i;
        }
    }
    return res;
}

那我们可以想到用一个支持修改的数据结构动态维护这个倍增数组，做到修改和查询都是 O(\log n) 复杂度，于是线段树（ segment tree ）就被发明了出来。

线段树基础

线段树的组成

线段树所需数组

struct treenode{
    int a;//线段树需要维护的各种信息，可以有多个
    //int lazy;(区间修改线段树需要用到，后面会讲)
    //int ls,rs;(动态开点线段树需要用到，后面会讲)
} tree[N*4];
//int rt[N] (可持久化线段树需要用到，后面会讲)

没什么好说的，维护线段树需要的各种信息

小 L：为什么我们要将数组开 N \times 4，满二叉树在底层节点个数为 N 的时候大小大概是 N \times 2 啊。

小 Y：这里留一个悬念，后面会说明为什么要开 4 倍数组。

pushup 函数

类似 ST 表（后文称倍增为 ST 表）的合并信息，线段树需要将两个儿子的信息进行合并，一般用一个 pushup 函数进行封装：

treenode pushup(treenode x,treenode y){
    treenode res;
    res.a=x.a+y.a;//合并方式，也可以是min，max等
    return res;
}

封装的好处是在其他需要用的地方可以直接调用函数而不是重新写一遍，保证代码美观的同时方便修改。

build 函数

线段树和 ST 表一样，一般需要一个构造函数（当然如果没有初始值就不需要建树），在这里我们用一个 build 函数解决。

void build(int p,int l,int r){
    if(l==r){tree[p].a=a[l];return;}
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    tree[p]=pushup(tree[p*2],tree[p*2+1]);
}

小 Y：这里就体现出来数组大小的作用了，为了建树方便，一般使用 p*2,p*2+1 来代表左右儿子，而这样最多需要约 4\times N 的大小，所以在建数组的时候要开 N*4。

update 函数（单点修改）

小 L：这应该怎么实现呢？

小 Y：我们来讲一个故事：如果，你写作业出现了一个错误，你会怎么做？

小 L：找到错误，并改正。

小 Y：但是这个错误并不好找，但是老师在某些页写上了“优”，”未订正“，可以帮你找到前面是否有错误，这时你应该怎么办？

小 L：按照老师的评语，慢慢缩小范围。

小 Y：但是老师还给你写了很多“未订正”啊。

小 L：再一层层找上去，将“未订正”改为“已订正”就行了。

（只是举个例子，实际上我们不应该随便改老师的评语）

小 Y：就是这个方法，试试实现吧。

void update(int p,int l,int r,int x,int v){
    if(l==r){tree[p].a+=v*(r-l+1);return;}
    int mid=(l+r)/2;
    if(x<=mid) update(p*2,l,mid,x,v);//需要修改左边
    else update(p*2+1,mid+1,r,x,v);//需要修改右边
    tree[p]=pushup(tree[p*2],tree[p*2+1]);//更新这个节点
}

query 函数（单点查询）

这个和 update 函数同理，如果询问点在左边就向左边询问，在右边就向右边询问（类似二分）。

treenode query(int p,int l,int r,int x){
    if(l==r)return tree[p];
    int mid=(l+r)/2;
    if(x<=mid) return query(p*2,l,mid,x);
    else return query(p*2+1,mid+1,r,x);
}

小 L：单点修改，单点查询……这不就是数组吗？

小 Y：没错，现在你可以尝试【模板】数组了。

小 L：……

query 函数（区间查询）

小 Y：假设老师将 6 个人分为一组，你是第三小组，那么你小组内的编号应该是什么？

小 L：13\~18，这也太简单了。

小 Y：那么如果老师要找编号在 8\~20 内的同学，你们组应该怎么做？

小 L：当然是全都去啊，我们组的人都包括在内。

小 Y：那现在在线段树的单点修改改为区间修改，并将终止条件转化为当前节点区间被全部包含在询问区间内，你试一下：

treenode query(int p,int l,int r,int L,int R){
    if(L<=l&&r<=R)return tree[p];
    //pushdown(p) 这个东西在区间修改的时候会讲到
    int mid=(l+r)/2;
    if(L>mid) return query(p*2+1,mid+1,r,L,R);
    if(R<=mid) return query(p*2,l,mid,L,R);
    return pushup(query(p*2,l,mid,L,mid),query(p*2+1,mid+1,r,mid+1,R));
}

到这里，线段树最最基础的部分就学完了，那么试一下 P3374【模板】树状数组 1，看看你有没有学会线段树吧。

小 L：等等，我们在学线段树，为什么要做树状数组的模板？

小 Y：等一下我们会学到区间修改，这时你就能做线段树的模板了。

pushdown 函数和懒惰标记

小 L：不是要学区间修改吗，怎么讲到这两个东西了？

小 Y：别急，慢慢来，这两个是区间修改的基础。

小 Y：如果老师会将明天要检查的人以及练习册页码告诉同学并严格按照前一天所说进行检查，同学们会怎么做？

小 L：那一定会等到老师检查到 Ta 再写要检查的那一页啊。

小 Y：那线段树的区间修改也是一样，可以先将要整个被修改的节点暂时压住不继续向下修改，等到其他需要向下传递的修改或者询问，再向下修改，利用结合律（如 a+2+3=a+5，\min(\min(a,b),c)=\min(a,\min(b,c)) 等方法来简化，即一个向下的 +2 操作和一个向下的 +3 操作可以被一个向下 +5 的操作等效替代）用尽量少的下传得到正确答案，由于这个方法就像在“偷懒”，因此被称为“懒惰标记”。

小 Y：在询问或查询子节点时，为了保证正确性，一般需要进行标记下传，即将这个节点的标记累加到两个子节点上，这个过程叫做“pushdown”。

小 L：我试试。

void pushdown(int p,int l,int r){
    if(tree[p].lazy){
        int mid=(l+r)/2;
        tree[p*2].a+=tree[p].lazy*(mid-l+1);
        tree[p*2+1].a+=tree[p].lazy*(r-mid);
        tree[p*2].lazy+=tree[p].lazy;
        tree[p*2+1].lazy+=tree[p].lazy;
        tree[p].lazy=0;
    }
}

update 函数（区间修改）

小 Y：然后这个事情就变得非常容易了，在完全覆盖这个节点的时候累加懒标记而不是继续下传就可以了。

void update(int p,int l,int r,int L,int R,int v){
    if(L<=l&&r<=R){
        tree[p].a+=v*(r-l+1);
        tree[p].lazy+=v;
        return;
    }
    pushdown(p,l,r);
    int mid=(l+r)/2;
    if(L<=mid) update(p*2,l,mid,L,R,v);//需要修改左边
    if(R>mid) update(p*2+1,mid+1,r,L,R,v);//需要修改右边
    tree[p]=pushup(tree[p*2],tree[p*2+1]);//更新这个节点
}

小 Y：现在可以看看 P3372【模板】线段树 1 和 P3373 【模板】线段树 2 了，期待你的 AC。

线段树思想

小 L：线段树的题也太难想了

小 Y：那是因为你没有会方法，一般情况下写线段树需要想好以下几个点：

  1. 信息与信息的合并（即 pushup）

  2. 信息与标记的合并（即 pushdown）

  3. 标记与标记的合并（即 update 中的标记累加以及 pushdown 的标记下传）

知道这几点之后线段树就非常简单了，其中单点修改只需要考虑第一条。

举几个例子：

:::info[P3373 【模板】线段树 2] 用两个标记来代表乘了多少和加了多少，即转化成 a\times b+c 的形式，而 (a+c)\times b 可以转化成 a\times b+b\times c，就好做了。 :::

:::info[P4513 小白逛公园] 这是一个经典问题（动态最大字段和），单点修改不需要维护懒惰标记，信息的合并我们可以通过维护最大字段和，左侧最大字段和，右侧最大字段和，区间和，合并就是：当前节点最大字段和 =\max( 左儿子最大字段和，右儿子最大字段和， 左儿子右侧最大字段和 + 右儿子左侧最大字段和 )，当前节点左侧最大字段和 =\max( 左儿子左侧最大字段和，左儿子区间和 + 右儿子左侧最大字段和 )，右侧同理。

treenode pushdown(treenode a,treenode b){
    treenode c;
    c.ma=max({a.ma,b.ma,a.rmax+b.max});
    c.lmax=max(a.lmax,a.sum+b.lmax);
    c.rmax=max(b.rmax,a.rmax+b.sum);
    c.sum=a.sum+b.sum;
    return c;
}

:::

权值线段树

小 Y：别看这个名字很难懂，其实就是对于权值开线段树，类似一个动态的桶，实际上在动态开点线段树和可持久化线段树上用的更多。

小 Y：到这里，我们的线段树基础就结束了，恭喜你已经会了线段树的基本操作：修改和查询，以及一种特殊的线段树：权值线段树。

线段树进阶

线段树二分

线段树二分（全局查询）

小 Y：给你一个序列，区间加，查询整个序列中最左的大于 k 的数，怎么做？

小 L：二分答案，就变成了区间查询最大值。

小 Y：复杂度呢？

小 L：O(n\log^2n)。

小 Y：但是序列长度和询问次数都是 10^6。

小 L：那应该怎么做呢？

小 Y：这时候我们可以用到类似二分线段树的线段树二分，从根节点开始，如果左面有答案，就向左查询，否则向右查询就可以了。

int query(int p,int l,int r,int k){
    if(a[p]<=k) return -1;
    if(l==r) return l;
    int mid=(l+r)>>1,x=query(p*2,l,mid,k);
    if(x!=-1) return x;
    else return query(p*2+1,mid+1,r,k);
}

线段树二分（区间查询）

小 Y：如果让你在一个区间内找最左的大于 k 的数，怎么做？

小 L：能不能将区间查询和线段树二分结合呢？

小 Y：那你试试吧。

int a[N*4];
int query(int p,int l,int r,int L,int R,int k){
    if(R<l||L>r||a[p]<=k) return -1;//脱离查询区间
    if(l==r) return l;
    int mid=(l+r)>>1,x=query(p*2,l,mid,L,R,k);
    if(x!=-1) return x;
    else return query(p*2+1,mid+1,r,L,R,k);
}

动态开点线段树

小 Y：如果给以一个长度是 10^9 的序列，但是没有初始值，你该怎么办？

小 L：凉拌。

小 Y：你再仔细想想？

小 L：好像需要修改的点也不多啊。

小 Y：就是这样，当我们需要修改到这个点的时候，再对这个点进行加点，也因此，我们不能通过普通的 p*2,p*2+1 表示左儿子和右儿子，而是需要用 ls,rs 来进行存储儿子的编号，就像这样：

treenode query(int &p,int l,int r,int L,int R){
    if(!p) p=++cnt;//新建这个节点，同时会改变调用函数时所用的ls或rs
    if(L<=l&&r<=R)return tree[p];
    pushdown(p)
    int mid=(l+r)/2;
    if(L>mid) return query(tree[p].rs,mid+1,r,L,R);
    if(R<=mid) return query(tree[p].ls,l,mid,L,R);
    return pushup(query(tree[p].ls,l,mid,L,mid),query(tree[p].rs,mid+1,r,mid+1,R));
}

此处的数组需要开 q \times \log n 而不是 n \times 4，因为单次修改最多修改 O(\log n) 个节点，同时因为引用关系，需要用一个变量 rt 来存储根节点。

可持久化线段树（主席树）

小 Y：如果你想要让你打的游戏可以回到一个选择之前，你会怎么做？

小 L：当然是给这个存档备份一下啊。

小 Y：那如果让你的线段树支持“回溯”操作，你应该怎么办？

小 L：那怎么给线段树节点备份呢？

小 Y：就像动态开点线段树一样在修改之前新开一个节点并在新开的节点上修改就可以了，就像这样：

void update(int &p,int l,int r,int x){
    int np=++cnt;tree[np]=tree[p];p=np;
    if(l==r){tree[p].a++;}
    if(x<=mid) add(tree[p].ls,l,mid,x);
    else add(tree[p].rs,mid+1,r,x);
    pushupup(p);
}

和动态开点线段树一样，需要存储根节点，但是因为可持久化线段树会新建节点，所以需要用一个数组 rt_i 表示第 i 此询问之后的根节点，调用的时候如下：

rt[i]=rt[i-1];update(rt[i],1,n,x);

利用这个可以实现可持久化数组，做题试试看吧：P3834【模板】可持久化线段树 2，P3919【模板】可持久化线段树 1（可持久化数组）（建议先做模板 2，因为模板 1 是可持久化数组，更难一些）。

小 L：那利用可持久化数组做的数据结构是不是也可持久化？

小 Y：是的，用可持久化数组做的并查集就是可持久化并查集……但是在这里不做过多介绍了。

李超线段树

小 Y：插入线段，询问在某一个横坐标上纵坐标最大的线段编号（按照插入顺序，从 1 开始），怎么做？

小 L：这也能用线段树吗？

小 Y：当然可以，这是李超线段树，大概思路就是：

  1. 若在左端点处 f 更优，那么 f 和 g 必然在左半区间中产生了交点，递归到左儿子中进行插入；

  2. 若在右端点处 f 更优，那么 f 和 g 必然在右半区间中产生了交点，递归到右儿子中进行插入。

  3. 若在左右端点处 g 都更优，那么 f 不可能成为答案，不需要继续下传。

放一个丑陋的源代码：

:::info[李超线段树]

inline node get(ld x0,ld y0,ld x1,ld y1){
    if(x0==x1)return (node){0,max(y0,y1)};
    ld k=(y1-y0)/(x1-x0),b=y1-k*x1;
    return (node){k,b};
}
inline ld f(int w,int x){return {a[w].k*x+a[w].b};}
inline void add(int k,int l,int r,int x,int y,int w){
    if(l==r){
        if(f(w,l)>f(t[k],l)) t[k]=w;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=l&&r<=y) {
        if(f(w,l)>f(t[k],l)&&f(w,r)>f(t[k],r)){t[k]=w;return;}
        if(f(w,l)<=f(t[k],l)&&f(w,r)<=f(t[k],r)) return;
        if(a[w].k>a[t[k]].k){
            if(f(w,mid)>f(t[k],mid)){add(k<<1,l,mid,x,y,t[k]);t[k]=w;}
            else add(k<<1|1,mid+1,r,x,y,w);
        }else{
            if(f(w,mid)>f(t[k],mid)){add(k<<1|1,mid+1,r,x,y,t[k]);t[k]=w;}
            else add(k<<1,l,mid,x,y,w);
        }
        return;
    }
    if(x<=mid)add(k<<1,l,mid,x,y,w);
    if(mid<y) add(k<<1|1,mid+1,r,x,y,w);
}
inline int Max(int p,int q,int x){
    if(f(p,x)!=f(q,x)){
        if(f(p,x)>f(q,x)) return p;
        return q;
    }
    return min(p,q);
}
inline int ask(int k,int l,int r,int x){
    if(l==r)return t[k];
    int mid=(l+r)>>1;
    if(x<=mid)return Max(t[k],ask(k<<1,l,mid,x),x);
    else return Max(t[k],ask(k<<1|1,mid+1,r,x),x);
}

:::

小 Y：没错这就是 P4097【模板】李超线段树 / [HEOI2013] Segment，快去看看吧，这种线段树常用于斜率优化 dp。

尾声

好了，关于线段树的常用操作，就讲到这里，希望大家都能学会这个几乎万能的数据结构，希望你能用线段树辅助你优化其他的算法（如 dp 等）。

我会时不时更新一些算法的详解，感兴趣的可以点一个关注支持一下 awa。