浅谈虚树优化线段树
前言
我们都知道动态开点权值线段树的空间复杂度是 的，但是很多题目中这样的空间是会被卡的，那我们能不能优化呢？
实现
看看下面这一棵树：
在上图中，红色节点使我们平常会开的点。
(相关资料图)
但是我们发现，其实只要维护绿色的点和红色的叶子结点。
其实，绿色节点就是所有叶子结点的虚树。
然后我们考虑如何维护虚树。
LCA
最基础的操作，目的是求解两个区间在线段树上的 LCA。
首先不难发现，两个区间的 LCA 等价于两个区间中任意取两点的 LCA，因为：
所以问题转化成求两个点的 LCA。
我们考虑记录下每个节点的编号，然后通过异或完求最低位的 的方式求出 LCA 的深度，然后记录下 LCA 右端点的编号。
在回收节点的时候可以释放储存右端点编号的空间，但是这里为了方便就不这样做了。
注意到这里记录右端点的编号可能会带来一定的空间常数，所以还有一种时间 但是空间常数小的写法：
ADD
目的是单点修改，考虑在线段树上便利，根据节点情况的不同大力分类讨论，建出新点与原来某个节点的 LCA。
QUERY
查询区间和，这一部分与普通线段树无异。
KTH
查询第 大，用来作为线段树上二分的一个模板，与普通线段树也无异。
MERGE
合并两棵线段树，这一部分需要根据合并的两棵线段树所管辖的区间来决定是否需要新建节点或者更改所管辖的区间来保证虚树上只存在叶子结点的 LCA 一性质。
SPLIT
这一部分需要递归不断处理，将一棵子树的左右儿子拆开再合并。
MAINTAIN
再前面的操作中会使一棵子树的根节点不断变化，但是我们插入查询时为了方便需要保证根节点管辖的区间是 ，所以需要此函数强制定义一个根节点。
代码整合
以下是【模板】线段树分裂的代码：
复杂度
空间复杂度 ，可以证明，有 个叶子节点的虚树最多只有 个节点，时间复杂度与正常线段树一致，是 的。
总结
如果您是巨佬的话一定可以看出来这样子构造出来的线段树和压缩 01Trie 在结构上大差不差，因此您也可以把它看作是压缩 01Trie 的一种变体实现。
标签：
