1. 线段树平衡树进阶
- 线段树分裂：按某个标准将线段树从某一条从根到叶子的路径处裂开，分成左、右两棵树。
- 时间复杂度证明：由于线段树分裂时仅和一条从根到叶子的路径上的点有关，而树高为 $O(\log{n})$，所以时间复杂度为 $O(\log{n})$，且分裂一次会新建 $O(\log{n})$ 个节点，所以分裂 $m$ 次的时空复杂度均为 $O(m \log{n})$。
- 线段树合并：将两棵线段树合并，对应节点的信息也合并。
- 实现：从根开始递归，如果当前节点两棵线段树都有值，则合并两棵线段树的信息，并删去其中一棵线段树的节点（也可以不删，视题目而定），向左右儿子递归；否则当前节点信息定为有值的线段树的节点信息，并返回。
- 时间复杂度证明：设所有待合并线段树总节点数为 $n$。考虑删去节点的写法。则合并信息的次数等于删去节点的次数，即 $O(n)$，而一次合并信息最多会递归到两次非合并信息的处理，则非合并信息的处理总次数也是 $O(n)$ 级别的，所以总时间复杂度为 $O(n)$。
- 势能线段树：更改原线段树的一些操作，通过势能分析得到正确复杂度。