线段树合并的线性空间做法

· · 算法·理论

考虑使用这个长得像平衡树的线段树。

合并的时候，如果有空节点直接返回，否则先将左右儿子合并，将另一个节点存的值插入下去。

空间显然是线性的。

时间复杂度考虑以每个值的深度之和为势能，插入的复杂度等于势能的增加量，而势能永远小于 O(n \log v)，所以总复杂度正确。

不过如果这个东西做线段树分裂的话会出现一定问题，如果保证每个点一定有值，需要做一个类似上旋的过程，把下面的值拿上来，但是这样会破坏势能分析，导致复杂度变为 O(n \log ^ 2 v)，不过也算提供了一种省空间，费时间的做法就是了。

如果不保证，则空间会因为分裂导致是 O(n \log v) 的。

压链 01-trie 可能也可以写差不多的东西，不过感觉会比较难写，但是压链 01-trie 做线段树分裂的复杂度可能更对一点。

压链 01-trie点数是 2倍，这个点数是一倍，有巨大空间优势。

模板题提交记录 （这份代码因为使用了 st 表求 lca，所以空间复杂度没变，跑得其实差不多快）