线段树漫谈

-1 前言

最近一直在研究树形数据结构，最后发现自己大概就能学明白一个线段树和一个树状数组。于是这次先来写一些线段树相关的东西。像是“平衡树漫谈”或者是“树形数据结构漫谈”的这种东西可能要一段时间以后了。

0 前置芝士

作为教程性质的文章为什么需要有前置芝士

• 线段树（最基础的）
• 树状数组（点修区间查）
• 其他的好像不需要了

2 线段树&树状数组基础

线段树，可能是OIer圈子中流传度最广，热度最高，最受人喜爱以及受迫害最多的数据结构。如下图：

那么这里默认已经通过了洛谷P3374 【模板】树状数组1和洛谷P3372 【模板】线段树1，也就是掌握了线段树和树状数组最基础的芝士。那么可以继续阅读下文。

2.1 线段树

线段树，其本身最关键的几个要素就是：结构，懒标记和科技。

先说结构。

线段树的本质是一颗二叉树，其每个节点都代表一个区间。并且其高度总维持在 $O(\log n)$ 级别，这是其能保证时间复杂度正确的关键所在。

性质：任意一个区间在线段树上可以被拆分成不超过 $\log n$ 个区间。

证明：感性理解待补。

很显然，这个东西是很多类似的树形数据结构能保证时间复杂度正确的关键性质。

3 线段树&树状数组基础应用

3.1 CDQ分治

这个东西我之前好像写过诶。

3.2 扫描线

4 线段树进阶

4.1 线段树分治

这部分的东西推荐去看我之前的文章。

4.2 线段树二分

个人感觉线段树二分是很基础的东西，基本是了解了线段树的基本结构就能很快想到的东西。但是不知道为什么还是放到线段树进阶这一块。

线段树二分的一个经典应用是动态全局第 $k$ 小。

例题：你需要维护一个可重集，要求支持以下三种操作：

1 x y：向该集合中添加 $x$ 个 $y$。

2 l r：查询 $\sum_{l\le i\le r} cnt_i$，其中 $cnt_i$ 表示 $i$ 在集合中的出现次数。

3 k：查询集合中第 $k$ 小的数，若不存在则输出 -1。

$1\le l,r,x,y,k\le 10^9$。

关于这个东西的想法是：首先发现维护的是集合中出现次数一类的东西，那么显然可以用权值线段树来做。然后发现值域巨大，但是因为可以动态开点所以不影响。

这样前两个操作都是简单的——分别对应权值线段树上的单点修改和区间查询。至于第三个操作，可以这么想：从线段树最顶上往下走，每次判断一下要找的这个数在左儿子值域内还是右儿子，也就是判断当前数的排名是否大于左儿子值域内数的数量，走到叶子节点就说明找到了答案。因为这样在线段树上找答案的过程类似二分，时间复杂度也就是线段树的树高 $O(\log n)$，所以得名线段树二分。

~~由于这里暂时没有线段树二分的例题，所以也暂时没有参考代码。~~待补。

4.3 线段树合并

通常意义下，提到的“线段树合并”应指“线段树的有交合并”。

线段树合并的意思就是把两个线段树合并起来，真的是字面意思，但是这里的合并有的时候并非简单的数值加法运算，在做类似线段树合并的题目时，维护某些复杂的合并运算就是题目的难点所在。

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

首先，因为这道题里面没有一边修改一边询问，所以做一下树上差分即可。然后问题就转化成了对于树上某几点的修改。考虑可以对于树上每个点都开一个权值线段树来维护，因为树上差分的每次操作至多涉及到树上 $2$ 个点的单点修改，每次单点修改至多产生 $\log n$ 个新线段树节点，所以空间复杂度 $O(q\log n)$，这么做是对的。

问题的关键在于最后做树上前缀和的过程，我们需要一种把线段树对应位置加起来的方式，这也就是合并操作定义为对应位置数值加法的线段树合并。那么假设目前合并的两颗线段树对应位置的节点是 $u$ 和 $v$，合并的过程事实上只需要讨论三种情况：

• $u,v$ 都不存在：直接跳过。
• $u,v$ 有一个存在：返回另一个。
• $u,v$ 都存在：将 $v$ 的数值合并到 $u$ 上，如有需要则回收 $v$ 的空间。

这事实上就是最基础的线段树合并，丑陋的示例代码如下：

int merge(int u,int v,int l,int r){//返回的是合并后的根节点编号
    if(!u)return v;
    if(!v)return u;
    if(l==r){
        seg[u]+=seg[v];
        return u; 
    }
    int mid=l+r>>1;
    lb[u]=merge(lb[u],lb[v],l,mid);
    rb[u]=merge(rb[u],rb[v],mid+1,r);
    pushup(u);
    return u;
}

此题的其他部分就是常规的线段树了。

题外话：我个人其实是没见过堆式存储的线段树合并的。

一道例题：P3224 [HNOI2012] 永无乡。

看到合并的操作很容易转化成并查集，而询问的操作就是对于每个连通块维护一个权值线段树，上面二分就可以了。然后两个连通块合并的时候对应的线段树也合并一下，是并不复杂的。

然而这个题用FHQ-Treap和线段树合并好像都可以，但是线段树合并做法好像还要比模板题简单一些。

非常需要注意的是这道题目输入数据的换行符是\r\n，因此使用快读和 getchar() 会出问题。

还有一道很重量级的线段树合并应用例题：P6773 [NOI2020] 命运。

推销一下我自己的文章：P6773题解。

4.4 线段树分裂

很多人看到字面就误以为线段树合并/分裂是一对互逆操作，但其实不然。一般意义下的“线段树合并”是“线段树的有交合并”，而“线段树的分裂”则是“线段树的无交分裂”或者也叫“线段树的按位置分裂”，根本不能混为一谈。

还有是这个东西能处理的很多题目好像FHQ-Treap也可以做。

例题：P5494 【模板】线段树分裂。

和上面的线段树二分类似的，我们可以把题目自然的转化为以下操作：

• 从一个权值线段树上分裂出区间 $[x,y]$ 的部分作为一颗新线段树。
• 把一颗线段树合并到另一颗上，合并操作为对应位置的数值加法。
• 单点修改。
• 区间和。
• 线段树二分。

后四种我们显然是都会的，而需要学习的就是第一种。

事实上线段树分裂的过程和线段树合并很相似，令目标区间为 $[L,R]$，原线段树上的当前节点是 $u$，对应的当前区间是 $[l,r]$，分裂出新线段树上的对应位置节点是 $v$，那么也只需要讨论下面几种情况：

• $[l,r]\subset[L,R]$：直接把节点 $u$ 挂到节点 $v$ 父亲的子树下，并把原来的节点 $u$ 回收清空。
• $[l,r]\cap [L,R]\neq \emptyset$：新开一个节点 $v$，继续向下分裂。
• $[l,r]\cap [L,R]= \emptyset$：直接返回。

本质其实就是这样。丑陋的示例代码如下：

void split(int &u,int &v,int l,int r,int L,int R){//separate v from u
    if(R<l||r<L)return;
    if(!u)return;
    if(!v)v=newnode();
    if(L<=l&&r<=R){
        v=u;u=0;
        return;
    }
    int mid=l+r>>1;
    split(lb[u],lb[v],l,mid,L,R);
    split(rb[u],rb[v],mid+1,r,L,R);
    pushup(u);
    pushup(v);
}

另外要说一句的是这个模板题真的恶心，也可能是我人傻常数大，空间卡了半天才过去。因此一定要注意线段树合并时，若有合并完没有的节点要记得回收处理。

5 进阶线段树

5.1 可持久化线段树

5.1.1 可持久化线段树基础

5.1.2 标记永久化

5.2 可持久化权值线段树

5.3 李超线段树

5.4 非递归式线段树（zkw线段树）

5.4.1 线段树与01Trie

5.4.2 zkw线段树

6 后记