重链剖分的另一个性质

我们大家都知道树的节点深度和是比树的节点高度和要大的，这个直观感受一下就能理解。什么时候这俩东西一样呢？答案是树形态形如一条链的时候。回忆重链剖分，重链剖分的一个性质是如果说我们把所有重链缩成一个点，形成的新树上节点深度最大是 \(\log n\) 级别，当然用完全二叉树就能把深度和卡到 \(n \log n\) 级别。联想一下刚刚的说法，你会发现完全二叉树和一条链简直是不共戴天的，所以这暗示我们重链剖分重构树的节点高度和可能有更好的性质。实际上这是 \(\mathrm O(n)\)。

形式化地描述一下这个问题。对于任意一棵树的重链剖分，对于每个轻儿子计算它子树内的节点最多需要跳几条重链才能到它，记录为它的高度，则所有轻儿子高度和是 \(\mathrm O(n)\) 的。我们可以这样考虑：统计有多少个节点高度为 \(i\)。注意到高度相同的节点彼此没有父子关系（废话），而重链剖分中高度为 \(i\) 的节点子树大小至少为 \(2^i\)，所以这个求和式是 \(\sum\limits_{i = 0}^{\lfloor\lg n\rfloor}i \cdot \lfloor \frac{n}{2^i} \rfloor\)，放缩以后随便捣鼓一下得到 \(\frac{n}{2^{\lfloor\lg n\rfloor}}\sum\limits_{i = 0}^{\lfloor\lg n\rfloor}(\lfloor\lg n\rfloor - i)2^i\)，后面的求和是经典线性建堆，这里还是推导一下：\(\sum\limits_{i=0}^{t}(t-i)2^i = \sum\limits_{p=1}^{t}\sum\limits_{i=0}^{p-1}2^i = \sum\limits_{p=1}^{t}2^p-1\le 2^{t+1}\)，于是实际上上面那个东西的上界是 \(2n\)，完全二叉树时候取满。

但是！注意到这时候我们说的 \(n\) 其实是重链条数也就是叶子个数。而卡满时说的完全二叉树也是把重链缩成一个点以后得到的重构树。所以实际上上界是比 \(2n\) 要更紧一些的。可惜后面的我不会分析了，留待高人。