全局平衡二叉树

全局平衡二叉树是一种可以处理树上链修改/查询的数据结构，可以做到：

还可以 O(\log n) 求最近公共祖先，子树修改，子树查询等，这些复杂度和重链剖分是一样的。

由于没有专门给这玩意准备的模板，我建议使用 P4211 [LNOI2014]LCA 作为模板题。这道题涉及到链加、链求和两种使用全局平衡二叉树复杂度优于朴素重链剖分的操作，也没有其他的操作，除此之外的转化也很简单。

其实直接用 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。然后我们按照这个求出这条重链的加权中点，把它作为二叉树的根，两边递归建树，并连上重边。

可能不是很好理解，代码如下：

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 一遍，常数大大大）。反正怎么写着顺手怎么来，代码如下

// 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 【模板】轻重链剖分

本题的完整代码。 由于全局平衡二叉树这种科技还不是很普及，会的人也不多，这道题的题解区里全是被吊打的树剖 O(n\log^2 n) 做法，写了一发 O(n\log n) 没特意卡常轻松拿到 132ms rk1（截至写这篇题解的时候）。并且代码比大部分的树剖线段树做法还短。