笔记汇总

和主席树一样，树套树采用 动态开点 的方式减少空间。

同样的，树套树采用与点分离的 永久化标记 处理区间的修改信息。

这类运用在 强制在线 是必要的。

如二维空间的修改查询，可采用 线段树套线段树，

不同区间序数关系查询，无修改时可用 线段树套权值线段树（效率较高）

有修改时若 非序数上（如在序列上某处）的修改只能用 线段树套平衡树。

线段树 是静态结构，平衡树 是动态结构，如果有结构上的改变，

我们则将 平衡树 作为外层。

实现（树上线段树）

即树上每一个结点都是一棵线段树（未开点的），

这主要是为了 $log$ 处理多维信息，也是 线段树合并 所常考的模型之一。

类似的还有 树上桶 $O(n)$

实现（线段树套线段树）

第一层线段树是一个区间，其中每一个结点都是一棵线段树（未开点的）

为了避免 $O(n)$ 复杂度的操作，所以在区间修改和查询时，

无论是内层还是外层都要标记永久化，标记与结点分离，查询时作为 函数附加值 携带。

所以结点上线段树也是 结点所代表的区间上 融合成的二维区间。