最近被各种乱七八糟的根号整的有点魔怔。重新系统总结一下线段树。

基础

线段树是一种维护区间信息的数据结构，绝大多数区间信息（如区间和，区间最值）都可以使用线段树高效维护。
若区间的合并操作是 \(O(1)\) 的，则线段树单点修改、区间查询操作是 \(O(\log n)\) 的。
若是带懒标记的线段树，如果懒标记下放操作是 \(O(1)\) 的，则线段树区间修改操作是 \(O(\log n)\) 的。
构建线段树最重要的操作是合并左右两个区间，也就是 push up 操作。
线段树的空间复杂度问题： 设有 \(n\) 个叶子节点，线段树的深度是 \(\lceil\log n\rceil\)，按照堆式存储（即 \(2u\) 是 \(u\) 的左儿子，\(2u+1\) 是 \(u\) 的右儿子）的方式，总节点个数 \(2^{\lceil\log n\rceil+1}-1\)，在 \(n\) 为 \(2\) 的整次幂加 \(1\) 时取到最大值 \(4n-5\)。所以平时线段树一定要开 \(4\) 倍空间。
\(k\) 叉线段树的复杂度为 \(O(k\log_kn)\)，其有 \(O(\log_kn)\) 层，每层要对 \(k\) 个节点进行操作。
常数中等。涉及区间修改且满足交换律的操作可以使用标记永久化减小常数。如果使用 zkw 线段树避免递归操作可以显著减小常数。
练手题：

经典套路

跨区间问题

小白逛公园

单点修改、区间最大子段和。
考虑如何合并两个区间。
新区间的最大子段和可能是左区间的最大子段和、右区间的最大子段和、左区间强制包含右端点的最大子段和加上右区间强制包含左端点的最大子段和。
区间强制包含左右端点的最大子段和可以通过区间和辅助维护。
总结一下，一个节点内需要维护：区间和、区间最大子段和、区间强制包含左端点的最大子段和、区间强制包含右端点的最大子段和。

1
2
3
4
5
6
7
8
9
10
11
struct node{
    int sum,maxn,maxl,maxr;
    friend node operator+(const node &x,const node &y){
        node res;
        res.sum=x.sum+y.sum;
        res.maxn=max({x.maxn,y.maxn,x.maxr+y.maxl});
        res.maxl=max(x.maxl,x.sum+y.maxl);
        res.maxr=max(y.maxr,y.sum+x.maxr);
        return res;
    }
};
trick：像这一类区间合并较为复杂的线段树，可以考虑将 + 重载，这样合并两个区间就更为方便了。
一定注意，这里的合并没有交换律。
习题：
[SCOI2010] 序列操作。

维护其他有结合律的信息

[国家集训队] 等差子序列

线段树维护哈希。

[THUSC 2017] 大魔法师

线段树维护矩阵。常数较大。

势能分析

一类题目看似操作复杂度很高，但是可以通过势能分析证明其复杂度是可接受的。

上帝造题的七分钟 2 / 花神游历各国

区间开方是非常难以维护的操作，但是注意到一个数 \(x\) 最多进行 \(O(\log \log x)\) 次操作就可以变为 \(1\)，之后的操作不会使数变得更小。所以我们可以在每个节点维护一个 \(tag\)，若当前区间内所有数均为 \(1\)，那么直接返回。
所以总体时间复杂度为 \(O(n\log \log V)\)。

线段树优化建图

有时候需要在一个点和一个区间之间连边。这时可以利用线段树的区间性质，降低空间复杂度。

权值线段树

通俗的理解就是在桶数组上开线段树。可以高效查询第 \(k\) 小等信息。

动态开点线段树

不再采用堆式存储，只在需要时，也就是第一次访问时创建节点。每个节点维护两个指针 \(ls\) 和 \(rs\)，表示当前节点的左右儿子。此时线段树最多只会创建 \(2n-1\) 个节点。不会像普通的堆式存储线段树一样存在空间浪费。
常数较大。
若需要区间修改，最好使用标记永久化以防止空间复杂度过大。

可持久化线段树

可持久化数组

开一个 \(root\) 数组，表示不同的版本。线段树的叶子节点即为我们可持久化的数组。上层的节点仅为了维持线段树的结构而存在。由于单点修改最多创建 \(O(\log n)\) 个节点，所以使用动态开点可以使得空间复杂度变得可接受。
可以使用可持久化数组实现可持久化并查集。注意不可使用路径压缩，否则会因为修改操作过多、创建过多新版本导致空间爆炸。
常数较大。

主席树

即可持久化权值线段树。可以解决的经典问题是静态区间第 \(k\) 小问题。利用前缀和/差分思想进行主席树上二分。
常数较大。

线段树合并

可以处理类似主席树能处理的问题。还能处理一类树上问题。
常数较大。

树套树

用于维护多维信息。常数巨大。

李超线段树

原理

我们以模板题为例讲解李超线段树工作原理。
首先我们有一个基于值域的线段树。
称一个线段在区间 \([l,r]\) 中最优当且仅当该线段完全覆盖 \([l,r]\) 且在 \(mid\) 处的值为所有线段最大。
线段树上每个节点保存对应区间的最优线段。注意：区间的线段不能保证对于区间内所有点都取到最优。
考虑在一个区间插入一个线段 \(f\)，若原区间有最优线段，设其为 \(f'\)：

  • 若区间内原本没有线段，则直接令 \(f\) 成为最优线段；

  • 若 \(f\) 完全位于 \(f'\) 上方（即“\(f\) 严格优于 \(f'\)”），直接替换掉；

  • 反之，\(f\) 不可能再成为最优线段，停止递归；

  • 若 \(f\) 部分优于 \(f'\)，则二者交点必然在区间内。按区间 \(mid\) 分开，则此时必然是：

    • 一个子区间内存在“严格优于”的关系；

    • 另一个子区间内是二者交点。递归更新。

对于第 3 种情况，不是区间最优线段的线段也有可能成为这个区间的答案。

单次查询操作时间复杂度 \(O(\log n)\)，全局修改时间复杂度 \(O(\log n)\)，区间修改时间复杂度 \(O(\log^2n)\)。李超线段树的常数较小。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
template<typename T>
inline T Abs(const T &x){return x<0?-x:x;}
constexpr int N=1e5+10;
constexpr double eps=1e-9;
struct line{
    double k,b;
    int id;
    inline double Y(int x){return x*k+b;}
};
struct segmenttree{
    bool flag;
    line L;
}tree[N<<2];
#define ls (u<<1)
#define rs (u<<1|1)
void modify(int u,int l,int r,int x,int y,line p){
    if(x<=l&&y>=r){
        double ly1=tree[u].L.Y(l),ry1=tree[u].L.Y(r);
        double ly2=p.Y(l),ry2=p.Y(r);
        if(!tree[u].flag) tree[u].L=p,tree[u].flag=1;
        else if(ly2-ly1>eps&&ry2-ry1>eps) tree[u].L=p;
        else if(ly2-ly1>eps||ry2-ry1>eps){
            int mid=(l+r)>>1;
            double midy1=tree[u].L.Y(mid);
            double midy2=p.Y(mid);
            if(midy2-midy1>eps) swap(tree[u].L,p);
            if(p.Y(l)>tree[u].L.Y(l)) modify(ls,l,mid,x,y,p);
            else modify(rs,mid+1,r,x,y,p);
        }
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) modify(ls,l,mid,x,y,p);
    if(y>mid) modify(rs,mid+1,r,x,y,p);
}
struct Res{double y;int id;};
Res query(int u,int l,int r,int x){
    Res res={tree[u].L.Y(x),tree[u].L.id};
    if(l==r) return res;
    int mid=(l+r)>>1;
    if(x<=mid){
        Res resl=query(ls,l,mid,x);
        if(resl.y>res.y||(Abs(resl.y-res.y)<eps&&resl.id<res.id))
            res=resl;
    }
    else{
        Res resr=query(rs,mid+1,r,x);
        if(resr.y>res.y||(Abs(resr.y-res.y)<eps&&resr.id<res.id))
            res=resr;
    }
    return res;
}

Segment Tree Beats

没用。学了考场上也调不出来。

参考资料：

https://oi-wiki.org/ds/seg/