「|「学习笔记」线段树合并「学习笔记」线段树合并

线段树合并普通线段树 $($ 无懒惰标记 $)$ 时间复杂度 & 空间复杂度
假设有 $2$ 棵线段树，它们的结点个数之和为 $s$，那么建树时间复杂度是 $O(s)$ 的。
【「|「学习笔记」线段树合并】为了简单表达，第 $i$ 棵线段树用 $\{ i \}$ 表示。
考虑 ${ x } $ 和 $\{ y \}$ 的合并：$($ 以下的结点指表示区间相同的结点，例如根结点都表示 $\mathrm{down} \sim \mathrm{up}$ $)$

情况 $1$ $\{ x \}$ 和 $\{ y \}$ 都存在的结点：
- 这 $2$ 个结点合并可以视作给其中 $1$ 个结点 $+1$；
- 因此时间复杂度为 $+1$ 的次数；在这个情况下，每个结点至多执行 $1$ 次 $+1$ 操作，至多有 $s$ 个结点，所以时间复杂度的上届是 $O(1 \times s) = O(s)$。
情况 $2$ $\{ x \}$ 和 $\{ y \}$ 中至少有一个不存在的结点：
- 此时它们的父亲结点一定都是存在的，不然就不会递归到这里了，同时也不需要往下递归了，对时间复杂度的贡献可以视作给父亲结点 $+1$；
- 在这个情况下，一个父亲结点至多执行 $2$ 次 $+1$ 操作，至多有 $s$ 个父亲结点，所以时间复杂度的上届是 $O(2 \times s) = O(2s)$。

综上所述：$2$ 棵线段树合并的时间复杂度为 $O(s)$。
这个结点可以推广到多棵线段树合并：记它们的结点个数之和为 $S$，那么线段树合并的时间复杂度为 $O(S)$，空间复杂度也为 $O(S)$。