算法学习笔记：线段树进阶

Populus_euphratica · 2023-10-29 21:23:39 · 个人记录

算法学习笔记：线段树进阶

壹.李超线段树

一、什么是李超线段树

李超线段树主要是用来维护在平面直角坐标系内直线关系的数据结构。举个例子，就是给定几条线段，然后询问在某条平行于 y 轴的直线与这些线段的交点的最值。如下图所示：

在这个平面直角坐标系中，有五条线段，而李超线段树可以求出在每个 x 坐标上线段的最值。就像这样（这里求的是最小值）：

二、李超线段树是如何进行操作的

首先，李超线段树既然叫线段树，那么其一定有与线段树一样的操作，也就是每次分成两段进行判断递归。

而李超线段树是一种相对暴力的算法，对于一个区间，定义区间最优势线段为在该区间的中点上的最值所在的线段。如果每次插入一条线段，就有一下几种情况：

在该区间内的两条线段相离：

这个条件也比较好判断，看左右端点即可。

如果上面的线段是该区间的区间最优势线段，那么就不进行改变，并结束递归。

如果下面的线段是该区间的区间最优势线段，那就用新加入的线段更新当前区间的最优势线段，并结束递归。
该区间的两条线段相交：

那么先确定中点：

更新区间最优势线段 mid 上的最大值，然后用劣势线段向下递归。

但也并不是所有两边的线段都需要向下继续递归。

就以当前的这张图来说，假设 a 现在是区间最优势线段，在右边，a 部分完全覆盖 b 部分，所以不用向下递归。在左边，b 线段在某个区间中可能比 a 优，那么把左边部分向下递归即可。

交点在 mid 左边的情况与此相同，在此不做赘述。

由于每次只会下传一半，所以其对于单条线段的修改与查询的时间复杂度均为 O(\log^2 n)。

三、李超线段树的具体实现

这里以P4097 【模板】李超线段树 / [HEOI2013] Segment为例：

#include<bits/stdc++.h>
#define int long long
#define mid ((l + r) >> 1)
using namespace std;
const int maxn = 39989;
const double eps = 1e-10;
int T, ans, lastans, cnt, tot, fir;
struct node1{
    double k, b;
}a[100010];//y = kx + b
struct Tree{
    int x, ls, rs;
}tree[400010];//线段树自己，左儿子，右儿子
bool cmp(int x, int y, int l){
    if(a[x].k * l + a[x].b - a[y].k * l - a[y].b > eps) return 1;
    if(a[y].k * l + a[y].b - a[x].k * l - a[x].b > eps) return 0;
    return x < y;
}//比较函数，由于模版精度卡的比较死，所以要专门写一个比较函数。
void modify(int &x, int l, int r, int L, int R, int k){
    if(L > r || R < l) return ;//超范围了，退出
    if(!x) x = ++cnt;//动态开点
    if(L <= l && r <= R){//新加入线段完全覆盖该区间
        if(cmp(tree[x].x, k, l) && cmp(tree[x].x, k, r)) return ;//原区间最优势线段完全覆盖新加入线段，退出
        if(cmp(k, tree[x].x, l) && cmp(k, tree[x].x, r)){
            tree[x].x = k;
            return ;
        }//新加入线段完全覆盖原区间最优势线段，更改区间最优势线段为新加入线段，退出。
        if(cmp(k, tree[x].x, mid)) swap(k, tree[x].x);//更新区间最优势线段为中点处较大的线段
        if(cmp(k, tree[x].x, l)) modify(tree[x].ls, l, mid, L, R, k);
        else modify(tree[x].rs, mid + 1, r, L, R, k);//因为劣势线段可能会在某个区间更优，找到是左右哪边，递归
        return;
    }
    modify(tree[x].ls, l, mid, L, R, k);
    modify(tree[x].rs, mid + 1, r, L, R, k);//没有完全覆盖，继续递归
}
void query(int x, int l, int r, int k){
    if(!x || k < l || k > r) return ;//这里没有值，或者是不在该区间内，退出
    if(cmp(tree[x].x, ans, k)) ans = tree[x].x;//取最大值
    if(l == r) return ;//已经找到一个点了，退出
    query(tree[x].ls, l, mid, k);
    query(tree[x].rs, mid + 1, r, k)//往左右递归
}
signed main(){
    ios::sync_with_stdio(false);
    cin >> T;
    while(T--){
        int op;
        cin >> op;
        if(!op){
            int x;
            cin >> x;
            x = (x + lastans - 1) % maxn + 1;//强制在线
            ans = 0;
            query(1, 1, maxn, x);//查询
            lastans = ans;
            cout << ans << '\n';
            continue;
        }
        int x, y, X, Y;
        cin >> x >> y >> X >> Y;
        x = (x + lastans - 1) % maxn + 1;
        X = (X + lastans - 1) % maxn + 1;
        y = (y + lastans - 1) % 1000000000 + 1;
        Y = (Y + lastans - 1) % 1000000000 + 1;//强制在线
        if(x > X) swap(x, X), swap(y, Y);
        if(x != X) a[++tot].k = 1.0 * (Y - y) / (X - x), a[tot].b = 1.0 * y - a[tot].k * x;
        //解一次函数解析式，y = kx + b
        else a[++tot].b = max(y, Y);//平行于 y 轴的直线特判一下
        modify(fir, 1, maxn, x, X, tot);
    }
    return 0;
}

贰.线段树合并

一、线段树合并是什么

线段树合并顾名思义就是把两颗线段树合并成为一颗线段树，也是一个非常暴力的过程。

其合并的是两颗权值线段树每个点上的权值，也就是对应点相加，最后两颗线段树合并为一颗。

二、线段树合并是如何操作的

首先需要知道的是线段树合并本身就是一个暴力的过程暴力地递归到左右端点，暴力地相加。

假设第一颗线段树为 a，第二课线段树为 b，对于把 b 合并到 a 上有具体有以下操作：

遍历到某个节点，a 这个这个节点中有值，b 中没有，结束递归。
遍历到某个节点，b 这个这个节点中有值，a 中没有，把 b 中的接到 a 上，结束递归。
往左右两边递归，最后合并。
当两个便利到的两个节点均为叶子节点时，直接把值相加。

至此，就把线段树合并的步骤讲完了，时间复杂度 O(n\log_n)。

三、线段树合并的具体实现

这里以 P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并为例。

这道题考虑把 x,y 两点之间将某种粮食数量加一改为以下四个操作：

将 x 到根节点的路径上的点的这种粮食数量 +1。
将 y 到根节点的路径上的点的这种粮食数量 +1。
将 lca(x, y) 到根节点的路径上的点的这种粮食数量 -1。
将 fa(lca(x, y)) 到根节点的路径上的点的这种粮食数量 -1。

对于每一个点开一颗线段树，询问时将线段树按照树上关系以此递归合并即可。代码如下：

#include<bits/stdc++.h>
#define mid ((l + r) >> 1)
using namespace std;
const int maxn = 1000010;
int n, m, cnt;
int s[100010], ans[100010];
struct tRee{
    int to, nxt;
}Tree[200010];
int head[100010], tot;
void add(int x, int y){
    Tree[++tot] = {y, head[x]};
    head[x] = tot;
}//变表存树
struct node{
    int x, ls, rs, sum, co;
}tree[6000010];//线段树
struct LcA{
    int dep[maxn], top[maxn], siz[maxn], son[maxn], fa[maxn];
    void dfs1(int x){
        dep[x] = dep[fa[x]] + 1;
        siz[x] = 1;
        for(int i = head[x] ; i ; i = Tree[i].nxt){
            int to = Tree[i].to;
            if(to == fa[x]) continue;
            fa[to] = x;
            dfs1(to);
            siz[x] += siz[to];
            if(siz[to] > siz[son[x]] || !son[x]) son[x] = to;
        }
    }
    void dfs2(int x, int tp){
        top[x] = tp;
        if(son[x])
            dfs2(son[x], tp);
        for(int i = head[x] ; i ; i = Tree[i].nxt){
            int to = Tree[i].to;
            if(to == fa[x] || to == son[x]) continue;
            dfs2(to, to);
        }
    }
    int lca(int x, int y){
        while(top[x] != top[y]){
            if(dep[top[x]] < dep[top[y]]) swap(x, y);
            x = fa[top[x]];
        }
        if(dep[x] > dep[y]) swap(x, y);
        return x;
    }
}LCA;//树链剖分求 lca
struct Linetree{

    void update(int x, int l, int r){
        if(tree[l].sum < tree[r].sum) 
            tree[x].sum = tree[r].sum, tree[x].co = tree[r].co;
        else tree[x].sum = tree[l].sum, tree[x].co = tree[l].co; 
    }//更新，用左右儿子中最大的那个区更新当前点的答案
    int merge(int x, int y, int l, int r){
        if(!x) return y;
        if(!y) return x;//其中一颗子树没有了，直接返回另一颗接上
        if(l == r){
            tree[x].sum += tree[y].sum;
            return x;//递归到叶子节点了，直接相加
        }
        tree[x].ls = merge(tree[x].ls, tree[y].ls, l, mid);
        tree[x].rs = merge(tree[x].rs, tree[y].rs, mid + 1, r);//继续向下递归
        update(x, tree[x].ls, tree[x].rs);//更新答案
        return x;
    }//线段树合并
    int build(int x, int l, int r, int co, int k){
        if(!x) x = ++cnt;//动态开点
        if(l == r){
            tree[x].sum += k;
            tree[x].co = co;
            return x;//到叶子节点了，赋值
        }
        if(co <= mid) tree[x].ls = build(tree[x].ls, l, mid, co, k);
        else tree[x].rs = build(tree[x].rs, mid + 1, r, co, k);//继续向下递归
        update(x, tree[x].ls, tree[x].rs);//更新答案
        return x; 
    }//建树
    void Ans(int x){
        for(int i = head[x] ; i ; i = Tree[i].nxt){
            int to = Tree[i].to;
            int f = LCA.fa[x];
            if(to == f) continue;
            Ans(to);
            s[x] = merge(s[x], s[to], 1, 100000);
        ans[x] = tree[s[x]].co;
        if(tree[s[x]].sum == 0) ans[x] = 0;//这里要特判一下，否则这里会是1
    }//递归求答案
}linetree;
signed main() {
    cin >> n >> m;
    for(int i = 1 ; i < n ; i++){
        int x, y;
        cin >> x >> y;
        add(x, y);  
        add(y, x);
    }//建树
    LCA.dfs1(1);
    LCA.dfs2(1, 1);//树剖
    for(int i = 1 ; i <= m ; i++){
        int x, y, co;
        cin >> x >> y >> co;
        int Lca = LCA.lca(x, y);
        s[x] = linetree.build(s[x], 1, 100000, co, 1);
        s[y] = linetree.build(s[y], 1, 100000, co, 1);
        s[Lca] = linetree.build(s[Lca], 1, 100000, co, -1);
        s[LCA.fa[Lca]] = linetree.build(s[LCA.fa[Lca]], 1, 100000, co, -1);//按照前面说的操作
    }
    linetree.Ans(1);//递归求答案
    for(int i = 1 ; i <= n ; i++) cout << ans[i] << '\n';//输出答案
    return 0;
}

算法学习笔记：线段树进阶

算法学习笔记：线段树进阶

壹.李超线段树

一、什么是李超线段树

二、李超线段树是如何进行操作的

三、李超线段树的具体实现

相关练习：

贰.线段树合并

一、线段树合并是什么

二、线段树合并是如何操作的

三、线段树合并的具体实现

相关习题