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

全局平衡二叉树

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

  • O(logn)O(\log n) 一条链整体修改
  • O(logn)O(\log n) 一条链整体查询

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

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

其实直接用 P3384 【模板】轻重链剖分 当模板也是可以的,也可以做到单次操作 O(logn)O(\log n),但是涉及到子树修改查询,比较难码(

下面我们用P4211当例题讲解。首先这个题区间 lca 深度和可以转化成给 [l,r][l,r] 内的每个点到根的链权值整体 +1+1,然后查询 zz 点到根的链的权值和。用差分就可以转化成 nn 次修改 2m2m 次查询。其他题解也讲的很清楚,这不是本篇题解重点。

以下正文开始


全局平衡二叉树的主要性质如下:

  1. 它由很多棵二叉树通过轻边连起来组成,每一棵二叉树维护了原树的一条重链,其中序遍历的顺序就是这条重链深度单调递增的顺序。每个节点都仅出现在一棵二叉树中。
  2. 边分为重边和轻边,重边是包含在二叉树中的边,维护的时候就像正常维护二叉树一样,记录左右儿子和父节点。轻边从一颗二叉树的根节点指向它所对应的重链顶端节点的父节点。轻边维护的时候“认父不认子”,即只能从子节点访问到父节点,不能反过来。注意,全局平衡二叉树中的边和原树中的边没有对应关系。

如果你学过 LCT 就能发现这几条性质和 LCT 非常相似,区别是用二叉树替代了 splay,用重边和轻边替代了实边和虚边。全局平衡二叉树就是静态化的 LCT。

  1. 算上重边和轻边,这棵树的高度是 O(logn)O(\log n) 级别的。这条是保证复杂度的性质。

蒟蒻深知没图的痛苦,所以画了两张图,第一张图是原树,以节点 11 为根节点。第二张图是建出来的全局平衡二叉树,其中虚线是轻边,实线是重边,一棵二叉树用红圈表示。


即使你不会 LCT 也没关系,全局平衡二叉树没有像 LCT 那么多操作(毕竟都是静态的,又没法 splay 和 access)。那么我们怎么建树呢,其实只要对着性质里所说的来就可以了。首先是像普通重链剖分一样,一次 dfs 求出每个节点的重儿子。然后从根开始,找到根节点所在的重链,对于这些点的轻儿子递归建树,并连上轻边。然后我们需要给重链上的点建一棵二叉树。我们先把重链上的点存到数组里,求出每个点轻儿子的 size 和 +1+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(nlogn)O(n\log n)。接下来我们可以证明树高是 O(logn)O(\log n) 的:考虑从任意一个点跳父节点到根。跳轻边就相当于在原树中跳到另一条重链,由重链剖分的性质可得跳轻边最多 O(logn)O(\log n) 条;因为建二叉树的时候根节点找的是算轻儿子的加权中点,那么跳一次重边算上轻儿子的 size 至少翻倍,所以跳重边最多也是 O(logn)O(\log n) 条。整体树高就是 O(logn)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(nlog2n)O(n\log^2 n) 做法,写了一发 O(nlogn)O(n\log n) 没特意卡常轻松拿到 132ms rk1(截至写这篇题解的时候)。并且代码比大部分的树剖线段树做法还短。