P4211 [LNOI2014]LCA | 全局平衡二叉树

# 全局平衡二叉树 全局平衡二叉树是一种可以处理树上链修改/查询的数据结构，可以做到： - $O(\log n)$ 一条链整体修改 - $O(\log n)$ 一条链整体查询 还可以 $O(\log n)$ 求最近公共祖先，子树修改，子树查询等，这些复杂度和重链剖分是一样的。 由于没有专门给这玩意准备的模板，我建议使用 [P4211 [LNOI2014]LCA](https://www.luogu.com.cn/problem/P4211) 作为模板题。这道题涉及到链加、链求和两种使用全局平衡二叉树复杂度优于朴素重链剖分的操作，也没有其他的操作，除此之外的转化也很简单。 其实直接用 [P3384 【模板】轻重链剖分](https://www.luogu.com.cn/problem/P3384) 当模板也是可以的，也可以做到单次操作 $O(\log n)$，但是涉及到子树修改查询，比较难码（ 下面我们用P4211当例题讲解。首先这个题区间 lca 深度和可以转化成给 $[l,r]$ 内的每个点到根的链权值整体 $+1$，然后查询 $z$ 点到根的链的权值和。用差分就可以转化成 $n$ 次修改 $2m$ 次查询。其他题解也讲的很清楚，这不是本篇题解重点。 以下正文开始 ------ 全局平衡二叉树的主要性质如下： 1. 它由很多棵二叉树通过轻边连起来组成，每一棵二叉树维护了原树的一条重链，其中序遍历的顺序就是这条重链深度单调递增的顺序。每个节点都仅出现在一棵二叉树中。 2. 边分为重边和轻边，重边是包含在二叉树中的边，维护的时候就像正常维护二叉树一样，记录左右儿子和父节点。轻边从一颗二叉树的根节点指向它所对应的重链顶端节点的父节点。轻边维护的时候“认父不认子”，即只能从子节点访问到父节点，不能反过来。注意，全局平衡二叉树中的边和原树中的边没有对应关系。 如果你学过 LCT 就能发现这几条性质和 LCT 非常相似，区别是用二叉树替代了 splay，用重边和轻边替代了实边和虚边。全局平衡二叉树就是静态化的 LCT。 3. 算上重边和轻边，这棵树的高度是 $O(\log n)$ 级别的。这条是保证复杂度的性质。 蒟蒻深知没图的痛苦，所以画了两张图，第一张图是原树，以节点 $1$ 为根节点。第二张图是建出来的全局平衡二叉树，其中虚线是轻边，实线是重边，一棵二叉树用红圈表示。   即使你不会 LCT 也没关系，全局平衡二叉树没有像 LCT 那么多操作（毕竟都是静态的，又没法 splay 和 access）。那么我们怎么建树呢，其实只要对着性质里所说的来就可以了。首先是像普通重链剖分一样，一次 dfs 求出每个节点的重儿子。然后从根开始，找到根节点所在的重链，对于这些点的轻儿子递归建树，并连上轻边。然后我们需要给重链上的点建一棵二叉树。我们先把重链上的点存到数组里，求出每个点轻儿子的 size 和 $+1$。然后我们按照这个求出这条重链的加权中点，把它作为二叉树的根，两边递归建树，并连上重边。 可能不是很好理解，代码如下： ```cpp std::vector<int> G[N]; int n, fa[N], son[N], sz[N]; void dfsS(int u) { sz[u] = 1; for (int v : G[u]) { dfsS(v); sz[u] += sz[v]; if (sz[v] > sz[son[u]]) son[u] = v; } } int b[N], bs[N], l[N], r[N], f[N], ss[N]; // 给b中[bl,br)内的点建二叉树，返回二叉树的根 int cbuild(int bl, int br) { int x = bl, y = br; while (y-x > 1) { int mid = (x+y) >> 1; if (2*(bs[mid]-bs[bl]) <= bs[br]-bs[bl]) x = mid; else y = mid; } // 二分求出按bs加权的中点。不使用二分而是直接扫一遍复杂度也对 y = b[x]; ss[y] = br-bl; // ss：二叉树中重子树的大小 if (bl < x) {l[y] = cbuild(bl, x); f[l[y]] = y; } if (x+1 < br) {r[y] = cbuild(x+1, br); f[r[y]] = y; } return y; } int build(int x) { int y = x; do for (int v : G[y]) if (v != son[y]) f[build(v)] = y; // 递归建树并连轻边，注意要从二叉树的根连边，不是从儿子连边 while (y = son[y]); y = 0; do { b[y++] = x; // 存放重链中的点 bs[y] = bs[y-1] + sz[x] - sz[son[x]]; // bs：轻儿子size和+1，求前缀和 } while (x = son[x]); return cbuild(0, y); } ``` 由代码可以看出建树的时间复杂度是 $O(n\log n)$。接下来我们可以证明树高是 $O(\log n)$ 的：考虑从任意一个点跳父节点到根。跳轻边就相当于在原树中跳到另一条重链，由重链剖分的性质可得跳轻边最多 $O(\log n)$ 条；因为建二叉树的时候根节点找的是算轻儿子的加权中点，那么跳一次重边算上轻儿子的 size 至少翻倍，所以跳重边最多也是 $O(\log n)$ 条。整体树高就是 $O(\log n)$ 的。 实际上关于全局平衡二叉树的部分就已经讲完了，剩下的链修改、链查询只需要从要操作的点往根跳，要操作某个点重链上比它深度小的所有点，就相当于在这条重链的二叉树里操作这个点左侧的所有点，可以拆成一系列子树操作，像维护普通二叉树一样维护子树和，打子树加标记就行。我使用的是标记永久化，其实也是可以标记用 pushdown，子树和用 pushup 的，不过可能不太好写（因为平时处理二叉树都是自上而下，这里是自下而上，可能需要先处理出跳的路径然后从上往下 pushdown 一遍，常数大大大）。反正怎么写着顺手怎么来，代码如下 ```cpp // a：子树加标记 // s：子树和（不算加标记的） int a[N], s[N]; void add(int x) { bool t = true; int z = 0; while (x) { s[x] += z; if (t) { a[x]++; if (r[x]) a[r[x]]--; z += 1 + ss[l[x]]; s[x] -= ss[r[x]]; } t = (x != l[f[x]]); if (t && x != r[f[x]]) z = 0; // 跳过轻边要清空 x = f[x]; } } int query(int x) { int ret = 0; bool t = true; int z = 0; while (x) { if (t) { ret += s[x] - s[r[x]]; ret -= 1ll * ss[r[x]] * a[r[x]]; z += 1 + ss[l[x]]; } ret += 1ll * z * a[x]; t = (x != l[f[x]]); if (t && x != r[f[x]]) z = 0; // 跳过轻边要清空 x = f[x]; } return ret; } ``` 顺便说一句，对于子树操作，就是要考虑轻儿子的，需要再维护一个包括轻儿子的子树和、子树标记，有需要可以去做 [P3384 【模板】轻重链剖分](https://www.luogu.com.cn/problem/P3384) [本题的完整代码。](https://www.luogu.com.cn/paste/3fbg3m9k) 由于全局平衡二叉树这种科技还不是很普及，会的人也不多，这道题的题解区里全是~~被吊打的~~树剖 $O(n\log^2 n)$ 做法，写了一发 $O(n\log n)$ 没特意卡常轻松拿到 132ms rk1（截至写这篇题解的时候）。并且代码比大部分的树剖线段树做法还短。