一种常数较小的能在单次 \(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;
}
链修改是好做的,但如果要维护子树信息就要维护考虑轻儿子的标记,比较麻烦,不如树剖(
标签:zson,return,int,ed,二叉树,平衡,now,全局,ls From: https://www.cnblogs.com/wwlwakioi/p/17815881.html