线段树的简单扩展及应用
注：这篇文章只开了个头就鸽了，如果真的准备学到点什么的话可以直接点上面这篇文章（
前言
线段树作为一种有效维护区间信息的数据结构，深受各位 OIer 以及毒瘤出题人的喜爱。
本文旨在记录笔者学习过程中遇到的普通线段树的扩展及其应用方法。
前置芝士
线段树
权值线段树
基础扩展
1.动态开点
权值线段树是替代平衡树（维护值域区间的一种数据结构。
不过它有一个缺点：基于线段树的建树结构，它的时间复杂度是 \(O(V)\) 的。
如果 \(V=10^9\) 甚至更大，那么普通的权值线段树就无法派上用场。
此时就需要动态开点权值线段树来维护。
动态开点的核心思想是：题目的值域很大，但插入数值的个数 \(n\) 一般都不会太大。
这个时候我们可以不建树，而是每需要插入一个节点，若对应值域区间为空节点，就新建结点。
不难发现，每次插入的时空复杂度均为 \(O(\log V)\)，故总的时空复杂度为 \(O(n\log V)\)。
需要注意的是，这种方法破坏了线段树的完全二叉树结构，所以原先线段树的编号方式不再适用。而是要用两个数组存储左右儿子的编号。
2.标记永久化
线段树区间操作的核心是 lazytag，然而，有一些特殊的线段树（如可持久化线段树），因为其结构特点，无法下传懒标记。
但这并不意味着懒标记失效，我们可以不下传懒标记，然后在查询过程中累加上根到节点的懒标记。
需要注意的是，除了区间修改，其余的操作都要满足操作的顺序对于答案无影响。
至于区间修改，只需另维护一个时间戳，统计路径上的时间戳最大值即可。
进阶扩展
1.线段树合并
线段树合并是线段树进阶扩展中较为基础的应用，即把两颗权值线段树合并到一起。
这个过程并不复杂，直接看代码中的注释。
要注意的是线段树合并必须配合动态开点实现。
int merge(int p,int q,int l,int r) {
if(!p||!q)return p | q;
int z = ++ tot;
if(l == r)return /*合并叶子结点信息*/,z;
int mid = l + r >> 1;
ls[z] = merge(ls[p] , ls[q] , l , mid);
rs[z] = merge(rs[p] , rs[q] , mid + 1 , r);
return /*合并左右结点*/,z;
}
注意的是，如果不改变原先的线段树结构，那么需要新开一个节点 \(z\)，用来存储，但这样空间消耗较大。
如果题目支持离线，也就是用完就扔，那么可以把所有的 z 改为 p，可以有效减少空间消耗。
先鸽了，以后再写，摆！
标签：标记,int,合并,线段,扩展,应用,权值 From： https://www.cnblogs.com/Royaka/p/16747045.html