线段树合并
普通线段树 \((\) 无懒惰标记 \()\)
时间复杂度 & 空间复杂度
假设有 \(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)\)。