如 CF600E 的线段树合并做法为例

每次将一个节点的所有儿子的线段树合并(带空间回收),如果每次都是直接合并可以被空间复杂度卡常 $\mathcal{n \log n}$,但是结合启发式合并的思想,先跑重儿子,那么空间复杂度应该是什么呢/kel

以下为口胡做法,不一定对

假定一颗线段树上的节点个数为 $k$,那么对于有 $2^i$ 个节点的子树所合并出来的线段树上的线段树节点的个数上限为 $k-2(n-\frac{n}{2^i})$

如果是对的求一个严格证明,否则求一个空间复杂度的证明/kel