全局平衡二叉树，其实说白了就是在树链剖分的基础上再次对每条链以相对平衡的方法再次重构成一颗固态的二叉树的形态，或者说在 LCT 的基础上把 Splay 换成满足全局平衡的二叉树，然后每步暴力往上跳即可。
以下是详细思想。
考虑 LCT 在静态树上常数很大，很大程度上是因为其 splay/access/makeroot 次数太多了。
如果我们能在 LCT 中按照一种合适的方法重建 Splay 的结构，把 Splay 换成某种静态的二叉树结构，则不用做 splay/access/makeroot 操作了，直接暴力跳父亲即可。
怎么换呢？
一种简单的想法是把每条链重构成一颗单独的线段树/静态平衡 BST。
这个东西其实就和普通的树剖区别不大了……单点修改/链查询复杂度容易发现是单次 \(O(\log^2n)\) 的。
为什么这个东西是两只老哥的呢？
因为在每条链上，平均每个节点的高度是 \(O(\log n)\) 的，而且这个东西可以被毒瘤出题人把 \(O(\log n)\) 条取满老哥的链首尾相接成链然后询问……
考虑如何避免出现这种几个取满老哥的位置首尾相接的毒瘤情况。
注意到平衡二叉树构造时是直接取中点拆成左右两段区间递归下去的，我们觉得这不好；一部分节点子树很大，你应该在这个点这里把它挪的高一点，避免在这里取满老哥。
考虑到中点其实就是一条链的重心，我们要把子树大小作为一个决定谁高谁低的指标的话，就应当求这条链的带权重心；原来求出的平衡二叉树就是一条链的点分树，而我们需要的全局平衡二叉树就是一条链的带权点分树，其中每个节点所在的子树对应重链上的一段区间。这点就和 Splay 维护 LCT 类似了。
因此算法流程就出来了：
- 进行轻重链剖分，把每条链提取出来。
- 对每个结点按轻子树大小之和定点权。
- 对每条重链，求出其带权点分树，即全局平衡二叉树。
- 对每条轻边，按类似 LCT 的方式，儿子认父亲，父亲不认儿子。
- 每条链的信息在平衡树上维护，单点修改/链查询直接暴力跳就好了。
这样，整个算法就完成啦！
容易证明，在这种结构上，树的高度是 \(O(\log n)\) 的，于是就完了。
当然，在随机数据下，这个算法实际运行效率和树剖差别不大……甚至有的时候常数还更大……
不过，如果使用这个算法来分治，我们就可以叫做树的链分治了。
习题：
代码咕咕。
标签：LCT,每条,Splay,二叉树,平衡,全局 From： https://www.cnblogs.com/myee/p/globally-balanced-binary-tree.html