浅谈全局平衡二叉树

首先，这个是GBT，不是GPT。其次，那个是ChatGPT，不是ChatGBT。

原理

我们先考虑一个经典的问题：单点修树上最大权独立集问题，也就是Luogu P4719 【模板】"动态 DP"&动态树分治。

使用树剖维护矩阵可以做到 \(O(n\log^2n)\) 的复杂度，可以通过 \(10^5\) 的数据。
那我们能不能把这个问题优化成 \(O(n\log n)\) 的呢？其实很简单，换成LCT，复杂度就是 \(O(n\log n)\) 的了，但是常数巨大……

我们发现在这类问题里面我们并没有使用LCT最核心的部分——断连边，而是使用了它 \(O(\log n)\) 提取树上链的特性。所以我们考虑把LCT换成静态的树结构以减小常数，于是全局平衡二叉树（Global Balance Tree）就诞生了，这也就是GBT有时会被称作静态LCT的原因。

我们考虑对于每一个条重链建一个BST，保证其中序遍历是链上从浅到深的顺序，轻链的连接方式和LCT一样，将每个BST的根的父亲定义为这个子树的链顶的父亲，也就是“认父不认子”。

对于一条到根的链的信息维护，就是不断跳父亲的过程，只需要在这过程中每个节点进行之多一次左孩子修改和当前节点修改即可。这样做一次的复杂度就是 \(O(dep\times S)\) 的，其中 \(dep\) 为树深度，\(S\) 为单次修改复杂度。

现在我们的问题就是如何保证 \(dep\) 是 \(O(\log n)\) 的。

参考树剖的复杂度证明，我们希望每跳 \(O(1)\) 次父亲就可以使的树的大小至少翻倍。比如说在跳轻链的时候，根据重链剖分的性质，树大小至少翻倍的。

于是，我们考虑给每一个点赋一个权值：所有轻儿子子树大小和+1。然后每次找到带权中点 \(mid\) 作为根，再递归处理 \([l,mid-1]\) 和 \([mid+1,r]\) 即可。不难发现这样子，在每个链的BST中跳一次，树的大小也是至少翻倍的。

这样，我们单次修改或者查找就是 \(O(\log n)\) 的了。

\(O(n\log n)\) 建树代码，其中 \(sum\) 数组为点权的前缀和：

int build_GBT(int l,int r)
{
    if(r<l) return 0;
    int mid=lower_bound(sum+l,sum+r+1,sum[r]+sum[l-1]>>1)-sum;
    if(s[mid].lson=build_GBT(l,mid-1)) s[s[mid].lson].fa=mid;
    if(s[mid].rson=build_GBT(mid+1,r)) s[s[mid].rson].fa=mid;
    s[mid].num=jz[mid];
    update(mid);
    return mid;
}

例题

感觉例题难点都是如何变成链上维护的问题，GBT都是用来替代重链剖分的……

Luogu P4751 【模板】"动态DP"&动态树分治（加强版）

单点修树上最大权独立集问题，\(n\leqslant 10^6,m\leqslant 3\times 10^6\)。

Luogu P9168 [省选联考 2023] 人员调度

后记

其实感觉实现很优秀的树剖是可以冲过去的。