算法-左偏树 (洛谷 P3377)

What’s it?

左偏树,是一种可并堆,可以在$log$的复杂度内将两个左偏树(堆)合并.

本文中的堆都是指小根堆.

How to use it?

Some Definitions

外节点:若一个点没有左儿子右儿子,则称这个节点为外节点.(不仅是叶子节点)

距离:一个节点到它最近的外节点的距离.

Some Properties

  1. 首先它是个堆,所以一个非叶子节点的权值小于它子树内的所有节点的权值.它也是棵二叉树.

  2. 那为什么左偏呢?因为我们设定每个节点左儿子的距离$\geq$右儿子的距离.

  3. 由性质2可以得出,一个节点的距离为其右儿子的距离+1.

  4. 另外,每个节点的左右子树都是左偏树.它是递归定义的.

接下来是一些非常重要非常屎的性质,关乎它的时间复杂度.

  1. 根的距离一定时(假设为$d$),节点数最少的左偏树是一颗完全二叉树,即有$2^{d+1}-1$个节点.

  2. 由性质5可以得出,一颗左偏树若有$n$个点,那么距离的最大值$\leq \log_2(n+1)-1$.

下面只给出性质6的证明:

设节点数为$n$,距离为$d$. 由性质5:
$\Rightarrow n\geq 2^{d+1}-1 \Rightarrow d+1\leq \log_2(n+1) \Rightarrow d\leq \log_2(n+1)-1$

Some Operation

Merge

口胡

这是左偏树最核心的操作. 设需合并的两棵树的根分别为$x,y$.

  1. 若$x/y$为空,直接返回非空的一个.

  2. 若$val_x<val_y$,为了保证大的接在小的下面,交换$x,y$.

  3. 因为它左偏,所以我们递归的将$x_{rs}$与$y$合并.

  4. 需修改$x_{rs}$的父亲为$x$.

  5. 若$d_{x_{ls}}<d_{x_{rs}}$,为保证左偏性质,交换$x_{ls},x_{rs}$.

  6. 更新$d_x$并返回$x$.

Code

1
2
3
4
5
6
7
8
9
int merge(int x, int y) {
if (x == 0 || y ==0) return x+y; //小技巧
if (t[x].val > t[y].val || t[x].val == t[y].val && x > y) swap(x, y);
t[x].rs = merge(t[x].rs, y);
t[t[x].rs].fa = x;
if (t[t[x].ls].dis < t[t[x].rs].dis) swap(t[x].ls, t[x].rs);
t[x].dis = t[t[x].rs].dis+1;
return x;
}

由性质6可以知道,复杂度是$O(d)$即$O(log_2(Size))$.

有了merge,什么操作都好做了.

Remove

口胡

设删的节点为$x$.(一般是根节点)

  1. 若一个点被删过了就直接结束.

  2. 将$x_{ls},x_{rs}$的父亲赋为0,即为新的根节点.

  3. 将$x$的左右儿子等信息清空.

  4. 将$x$原来的左右儿子合并.

Code

1
2
3
4
5
6
7
8
void remove(int x) {
if (t[x].val < 0) return;
int lc = t[x].ls, rc = t[x].rs;
t[x].ls = t[x].rs = t[x].dis = 0;
t[x].val = -1; //若有负权,请千万不要赋成-1
t[lc].fa = t[rc].fa = 0;
merge(lc, rc);
}

Insert

口胡

将新节点当作一棵单独的左偏树,初始化信息,与要插入进去的左偏树合并

Code

1
2
3
4
int insert(int val, int x) {
t[++n] = (node){0, 0, n, 0, val};
return merge(n, x);
}

Complete Code

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
const int inf = 0x3f3f3f3f;
struct node {
int ls, rs, fa, dis, val;
} t[maxn+10];
int n, m;
int find(int x) {
while (t[x].fa)
x = t[x].fa;
return x;
}
int merge(int x, int y) {
if (x == 0 || y ==0) return x+y;
if (t[x].val > t[y].val || t[x].val == t[y].val && x > y) swap(x, y);
t[x].rs = merge(t[x].rs, y);
t[t[x].rs].fa = x;
if (t[t[x].ls].dis < t[t[x].rs].dis) swap(t[x].ls, t[x].rs);
t[x].dis = t[t[x].rs].dis+1;
return x;
}
void remove(int x) {
if (t[x].val < 0) return;
int lc = t[x].ls, rc = t[x].rs;
t[x].ls = t[x].rs = t[x].dis = 0;
t[x].val = -1;
t[lc].fa = t[rc].fa = 0;
merge(lc, rc);
}
/*int insert(int val, int x) {
t[++n] = (node){0, 0, n, 0, val};
return merge(n, x);
}*/
int main() {
t[0].dis = -1;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%d", &t[i].val);
for (int i = 1; i <= m; ++i) {
int opt, x, y;
scanf("%d", &opt);
if (opt == 1) {
scanf("%d%d", &x, &y);
if (t[x].val < 0 || t[y].val < 0) continue;
x = find(x); y = find(y);
if (x != y) merge(x, y);
} else {
scanf("%d", &x);
if (t[x].val < 0) printf("-1\n");
else {
x = find(x);
printf("%d\n", t[x].val);
remove(x);
}
}
}
return 0;
}

Why TLE?

当你看完上面的内容,打出大致如上的代码然后兴致勃勃地交到洛谷的P3377(左偏树模板题)后,你会发现最后一个点TLE了,而且吸氧也没有用.

而这组数据在之前是没有的.是哪位好心人提交的hack数据?!

The reason and The treatment

其实你有没有发现,上面的代码中的$find(x)$并没有用路径压缩,因为如果我们路径压缩,并把根节点删除后,它的后代们会”群龙无首”.它们的父亲都指向着一个空节点.

1
2
3
4
5
int find(int x) {
while (t[x].fa)
x = t[x].fa;
return x;
}

怎么办呢?

路径压缩肯定是要的,我们直能在删除的时候做些手脚,修改成如下的代码:

1
2
3
4
5
6
7
8
void remove(int x) {
if (t[x].val < 0) return;
t[t[x].ls].fa = t[x].ls; //改变1
t[t[x].rs].fa = t[x].rs; //改变2
t[x].fa = merge(t[x].ls, t[x].rs); //改变3
t[x].ls = t[x].rs = t[x].dis = 0;
t[x].val = -1;
}

这时,我们将被删的根节点的父亲设为新的根节点,这样,那些指向它的节点会顺着这个方向最终指向新的根.

另外也要注意在开始初始化每个点的父亲.

New Code

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
const int inf = 0x3f3f3f3f;
struct node {
int ls, rs, fa, dis, val;
} t[maxn+10];
int n, m;
int find(int x) {
return x == t[x].fa ? x : t[x].fa = find(t[x].fa);
}
int merge(int x, int y) {
if (x == 0 || y ==0) return x+y;
if (t[x].val > t[y].val || t[x].val == t[y].val && x > y) swap(x, y);
t[x].rs = merge(t[x].rs, y);
t[t[x].rs].fa = x;
if (t[t[x].ls].dis < t[t[x].rs].dis) swap(t[x].ls, t[x].rs);
t[x].dis = t[t[x].rs].dis+1;
return x;
}
void remove(int x) {
if (t[x].val < 0) return;
t[t[x].ls].fa = t[x].ls;
t[t[x].rs].fa = t[x].rs;
t[x].fa = merge(t[x].ls, t[x].rs);
t[x].ls = t[x].rs = t[x].dis = 0;
t[x].val = -1;
}
/*int insert(int val, int x) {
t[++n] = (node){0, 0, n, 0, val};
return merge(n, x);
}*/
int main() {
//freopen("P3377.in", "r", stdin);
//freopen("P3377.out", "w", stdout);
t[0].dis = t[0].val = -1;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d", &t[i].val);
t[i].fa = i;
}
for (int i = 1; i <= m; ++i) {
int opt, x, y;
scanf("%d", &opt);
if (opt == 1) {
scanf("%d%d", &x, &y);
if (t[x].val < 0 || t[y].val < 0) continue;
x = find(x); y = find(y);
if (x != y) merge(x, y);
} else {
scanf("%d", &x);
if (t[x].val < 0) printf("-1\n");
else {
x = find(x);
printf("%d\n", t[x].val);
remove(x);
}
}
}
return 0;
}

感谢这组hack数据让我们发现了问题并加以改进!

THANK YOU FOR READING THIS!