全局平衡二叉树

一种常数较小的能在单次 \(O(\log n)\) 时间内解决链修改链查询的数据结构。

普通的 LCT 也是 \(O(\log n)\) 的，但是常数巨大。原因是它用辅助树维护了一个动态的虚实链剖分，在没有动态加边删边的问题中这显然是没有必要的。我们考虑将 LCT 强行静态化来减小长度。

具体的，我们仍用类似 LCT 的结构来维护树的一个轻重链剖分。对于一条重链，我们不用 splay 而是用一棵静态的二叉搜索树。每次将点权设为轻子树的 \(siz\) 和，求出链的带权重心，往两边递归建树。建树的代码：

inline int build(int now) {
	vector<int> s;
	for (int i = now; i; i = zson[i]) vis[i] = 1;
	for (int i = now; i; i = zson[i]) {
		for (int j = ed[i].head; j; j = ed[j].nxt) {
			int v = ed[j].to;
			if (vis[v]) continue;
			fa[build(v)] = i;
		} s.push_back(i); lsiz[i] = siz[i] - siz[zson[i]];
	}
	auto calc = [&s](auto &f, int l, int r) {
		if (l > r) return 0;
		ll sum = 0, cnt = 0;
		for (int i = l; i <= r; ++i) sum += lsiz[s[i]];
		for (int i = l; i <= r; ++i) {
			cnt += lsiz[s[i]];
			if (2 * cnt >= sum) {
				rs(s[i]) = f(f, l, i - 1);
				ls(s[i]) = f(f, i + 1, r);
				if (ls(s[i])) fa[ls(s[i])] = s[i];
				if (rs(s[i])) fa[rs(s[i])] = s[i];
				update(s[i]);
				return s[i];
			}
		}
		return 0;
	}; int rt = calc(calc, 0, s.size() - 1);
	return rt;
}

链修改是好做的，但如果要维护子树信息就要维护考虑轻儿子的标记，比较麻烦，不如树剖（