Euler Tour Tree
一般提到动态树,我们会不约而同的想到 LCT,这算是比较通用,实用,能力较为广泛的一种写法了。当然,掌握 LCT 就需要熟悉掌握 Splay 和各种操作和知识。ETT(中文常用称呼:欧拉游览树)是一种及其睿智且暴力,可以用暴力数据结构维护的一种除了能胜任普通动态树的 Link & Cut 操作还可以支持换子树操作(此操作 LCT 无法完成)的动态树。
大家对这括号序很熟悉吧,如:
其括号序为:1 2 5 5 6 6 2 3 3 4 7 8 8 7 4 1
。
括号序其实是一个父亲包含儿子的一种树的顺序。
然后我们看一下,如果把 4
的子树移给 3
会怎样?如图:
原图括号序:1 2 5 5 6 6 2 3 3 4 7 8 8 7 4 1
后者括号序:1 2 5 5 6 6 2 3 7 8 8 7 3 4 4 1
可以发现,7 8 8 7
平移到了 3
的后面,而 4
合拢。这就是所谓换子树操作(同样可以用于 Link & Cut 操作)。现在只需要一个数据结构可以做到区间平移且维护一些值,众大佬肯定会说用 Splay,其确实效率很高,不过这里用块状链表维护会简单很多,对于一些数据低于
那怎么维护点到根的信息呢?
其实仔细想想,DFS 序也可以达到平移的效果,那么为什么需要括号序?其实,假如你要查询图中 1
到 8
的和,那么你从括号序中 1
到 8
(第一个出现的)中出现两次的数的贡献抹去。如果维护的是 xor,那么直接 xor 两次即可。如果维护的是 sum,那么第一个出现的数字的贡献为正,第二个为负,然后用块状链表维护区间和即可。
用块状链表后除了单点修改是
ETT 不支持换根操作。对于链(区间)修改,分为两种情况,一是贡献相同(如 xor)是可以的,二是贡献不同(如 sum)是不行的。现在的主流做法毕竟是 LCT,所以这些操作比较多,在避开这种操作的情况下运用这种做法还是不错的。
注:标准的 ETT(用欧拉回路而不是 DFS 括号序实现)是支持换根操作的,但是实现较为复杂。
例题 星系探索 参考代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 | /*
虽然上文提到过块状链表实现 ETT
在某些情况下可能较简单,但对于此题块状链表复杂度有可能无法通过而且实现较繁琐,所以这份代码采用
FHQ Treap 实现。
*/
#include <bits/stdc++.h>
#define N 1000000
#define int long long
using namespace std;
/*FHQ TREAP*/
int rt, tot, f[N], rnd[N], ls[N], rs[N], siz[N], tag[N], val[N], sum[N], pd[N],
pds[N];
void pushup(int x) {
siz[x] = siz[ls[x]] + siz[rs[x]] + 1;
sum[x] = sum[ls[x]] + sum[rs[x]] + val[x];
pds[x] = pds[ls[x]] + pds[rs[x]] + pd[x];
}
void link(int x, int c, int y) {
if (c)
rs[x] = y;
else
ls[x] = y;
if (y) f[y] = x;
pushup(x);
}
int newNode(int x, int y) {
siz[++tot] = 1;
val[tot] = sum[tot] = x;
pd[tot] = pds[tot] = y;
rnd[tot] = rand();
return tot;
}
void setTag(int x, int v) {
tag[x] += v;
sum[x] += v * pds[x];
val[x] += v * pd[x];
}
void pushdown(int x) {
if (ls[x]) setTag(ls[x], tag[x]);
if (rs[x]) setTag(rs[x], tag[x]);
tag[x] = 0;
}
void split(int now, int k, int &x, int &y) {
f[now] = 0;
if (!now) {
x = y = 0;
return;
}
pushdown(now);
if (siz[ls[now]] + 1 <= k) {
x = now;
split(rs[now], k - siz[ls[now]] - 1, rs[x], y);
link(x, 1, rs[x]);
} else {
y = now;
split(ls[now], k, x, ls[y]);
link(y, 0, ls[y]);
}
}
int merge(int x, int y) {
if (!x || !y) return x | y;
if (rnd[x] < rnd[y]) {
pushdown(x);
link(x, 1, merge(rs[x], y));
return x;
} else {
pushdown(y);
link(y, 0, merge(x, ls[y]));
return y;
}
}
int rnk(int x) {
int c = 1, ans = 0;
while (x) {
if (c) ans += siz[ls[x]] + 1;
c = (rs[f[x]] == x);
x = f[x];
}
return ans;
}
/*ETT*/
int s[N], e[N];
void add(int x, int v) {
int a, b, c;
split(rt, rnk(s[x]) - 1, a, b);
split(b, rnk(e[x]) - rnk(s[x]) + 1, b,
c); //这里 b 是我们要进行操作的子树的括号序列。
setTag(b, v);
rt = merge(merge(a, b), c);
}
int query(int x) {
int a, b;
split(rt, rnk(s[x]), a, b);
int ans = sum[a];
rt = merge(a, b);
return ans;
}
void changeFa(int x, int y) {
int a, b, c, d;
split(rt, rnk(s[x]) - 1, a, b);
split(b, rnk(e[x]) - rnk(s[x]) + 1, b, c);
a = merge(
a,
c); //因为我们确定不了要设置为父亲的节点在括号序列中的哪边,所以先把两边合并。
split(a, rnk(s[y]), a, d);
rt = merge(merge(a, b), d); //把要进行操作的子树放在父亲括号序列的最前面。
}
/*main function*/
int n, m, w[N];
vector<int> v[N];
void dfs(int x) {
rt = merge(rt, s[x] = newNode(w[x], 1));
for (auto to : v[x]) dfs(to);
rt = merge(rt, e[x] = newNode(-w[x], -1));
}
signed main() {
cin >> n;
for (int i = 2; i <= n; i++) {
int f;
cin >> f;
v[f].push_back(i);
}
for (int i = 1; i <= n; i++) cin >> w[i];
dfs(1);
cin >> m;
for (int i = 1; i <= m; i++) {
char c;
cin >> c;
if (c == 'Q') {
int d;
cin >> d;
cout << query(d) << endl;
} else if (c == 'C') {
int x, y;
cin >> x >> y;
changeFa(x, y);
} else {
int p, q;
cin >> p >> q;
add(p, q);
}
}
return 0;
}
|
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用