【学习笔记】左偏树

只会写不会用系列.jpeg

嗯…就当作是复习了233…时隔好几个月(其实就两个月)才想起来要整理。

关于左偏树

首先是整理自己想出来的几个梗

  • $\mathcal{To~be~(left) ~or~not ~to~be~(left), this~is ~a~question}$ 左偏还是右偏,这是个问题(哈姆雷特梗)。
  • Hell ! Where is my Left Leaning Tree? 该死,我的左偏树向右偏了。
  • 左偏树是1个log,右偏树也是1个log,那我左右都偏是不是就会更快!(恭喜你建出了一棵满二叉树)
  • 讲个鬼故事:每棵树都是下偏树。
  • 其实,左耳离心脏更近,所以甜言蜜语麻烦合并到左偏树里吧。(《左耳》梗)

好吧我承认不是很好笑

呐,下面进入正题。左偏树,一种可以合并的堆状结构,支持 insert/remove/merge 等操作。稳定的时间复杂度在 $\Theta(\log n)$ 的级别。对于一个左偏树中的节点,需要维护的值有 distvalue。其中 value 不必多说,dist 记录这个节点到它子树里面最近的叶子节点的距离,叶子节点距离为 0。

首先,他有以下几个喜闻乐见的性质:

一个节点的 value 必定(或小于)左右儿子的 value (堆性质)
一个节点的左儿子的 dist 不小于右儿子的 dist (左偏性质)
一个节点的距离始终等于右儿子 +1 。

那么这就可以推出以下性质:

推论:任何时候,节点数为 $n$ 的左偏树,距离最大为 $\log (n+1)-1$ .

对于一棵距离为定值 $k$ 的树,点数最少时,一定是一棵满二叉树。这是显然的。因为对于每个节点,如果想要有最少的儿子,那么起码要做到左儿子的数量等于右儿子的数量。那么对于他的逆命题也是成立的—— “若一棵左偏树的距离为 $k$,则这棵左偏树至少有 $2^{k+1}-1$ 个节点”。

所以会有

emmm 这可是一个很美妙的性质啊。

基本操作

Merge

这是整个左偏树的重头戏,时间复杂度稳定在一个 $\log$,其主要思想就是不断把新的堆合并到新的根节点的右子树中——因为我们的右子树决定“距离”这个变量,而距离又一定保证在 $\log$ 的复杂度内,所以不断向右子树合并。

大体思路(以小根堆为例),首先我们假设两个节点 $x$ 和 $y$,$x$ 的根节点的权值小于等于 $y$ 的根节点(否则 swap(x,y)),把 $x$ 的根节点作为新树 $\rm Z$ 的根节点,剩下就是合并 $x$ 的右子树和 $y$ 了。

合并了 $x$ 的右子树和 $y$ 之后,当 $x$ 的右子树的距离大于 $x$ 的左子树的距离时,为了维护性质二,我们要交换 $x$ 的右子树和左子树。顺便维护性质三,所以直接 $dist_x = dist_{rson(x)}+1$ .

1
2
3
4
5
6
inline int Merge(int x, int y){
if (!x || !y) return x + y ;
if (S[x].val > S[y].val || (S[x].val == S[y].val && x > y)) swap(x, y) ;
rs = Merge(rs, y) ; if (S[ls].dis < S[rs].dis) swap(ls, rs) ;
S[ls].rt = S[rs].rt = S[x].rt = x, S[x].dis = S[rs].dis + 1 ; return x ;
}

我们观察,我们是不断交替拆分右子树,由推论可得我们的距离不会大于

这个地方比较喜闻乐见的是需要存$root$,即需要路径压缩。不路径压缩的话,寻一次$rt$就是$\Theta(n)$的了,复杂度是不对的 但似乎Luogu的模板,不路径压缩会更快

Pop

……$pop$的话,乱搞就好了$233$

1
2
3
inline void Pop(int x){ 
S[x].val = -1, S[ls].rt = ls, S[rs].rt = rs, S[x].rt = Merge(ls, rs) ;
}

注意到删除操作其实是把当前应该被删除的 $rt$ 当做了一个虚点,加入了新的没有 $rt$ 的子树内,这样就可以使得那些原来连在 $rt$ 上的点,再找一次 fa 的时候就会被路径压缩到新的根上。

然后就是总代码:

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
struct Tree{
int dis, val, Son[2], rt ;
}S[MAXN] ; int N, T, A, B, C, i ;

inline int Merge(int x, int y) ;
int my_swap(int &x, int &y){ x ^= y ^= x ^= y ;}
inline int Get(int x){ return S[x].rt == x ? x : S[x].rt = Get(S[x].rt) ; }
inline void Pop(int x){ S[x].val = -1, S[ls].rt = ls, S[rs].rt = rs, S[x].rt = Merge(ls, rs) ; }
inline int Merge(int x, int y){
if (!x || !y) return x + y ; if (S[x].val > S[y].val || (S[x].val == S[y].val && x > y)) swap(x, y) ;
rs = Merge(rs, y) ; if (S[ls].dis < S[rs].dis) swap(ls, rs) ; S[ls].rt = S[rs].rt = S[x].rt = x, S[x].dis = S[rs].dis + 1 ; return x ;
}
int main(){
cin >> N >> T ; S[0].dis = -1 ;
for (i = 1 ; i <= N ; ++ i)
S[i].rt = i, scanf("%d", &S[i].val) ;
for (i = 1 ; i <= T ; ++ i){
scanf("%d%d", &A, &B) ;
if (A == 1){
scanf("%d", &C) ;
if (S[B].val == -1 || S[C].val == -1) continue ;
int f1 = Get(B), f2 = Get(C) ; if (f1 != f2) S[f1].rt = S[f2].rt = Merge(f1, f2) ;
}
else {
if(S[B].val == -1) printf("-1\n") ;
else printf("%d\n", S[Get(B)].val), Pop(Get(B)) ;
}
}
}

一点问题

问题大概就是路径压缩……

$LuoguP3377$很不负责任地处了数据,导致以下这份代码可以过:

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
using namespace std ;
struct Tree{
int dis, val, F, Son[2] ;
}S[MAXN] ;
int N, T, A, B, C, i ;

inline int Merge(int x, int y) ;
int my_swap(int &x, int &y){ x ^= y ^= x ^= y ;}
int Get(int x){ while(S[x].F) x = S[x].F ; return x ; }
inline void Pop(int x){ S[x].val = -1, S[ls].F = S[rs].F = 0, Merge(ls, rs) ; }
inline int Merge(int x, int y){
if (!x || !y) return x + y ; if (S[x].val > S[y].val || (S[x].val == S[y].val && x > y)) swap(x, y) ;
rs = Merge(rs, y), S[rs].F = x ; if (S[ls].dis < S[rs].dis) swap(ls, rs) ; S[x].dis = S[rs].dis + 1 ; return x ;
}
int main(){
cin >> N >> T ; S[0].dis = -1 ;
for (i = 1 ; i <= N ; ++ i) scanf("%d", &S[i].val) ;
for (i = 1 ; i <= T ; ++ i){
scanf("%d%d", &A, &B) ;
if (A == 1){
scanf("%d", &C) ;
if (S[B].val == -1 || S[C].val == -1 || B == C) continue ;
int f1 = Get(B), f2 = Get(C) ; Merge(f1, f2) ;
}
else {
if(S[B].val == -1) printf("-1\n") ;
else printf("%d\n", S[Get(B)].val), Pop(Get(B)) ;
}
}
return 0 ;
}

一切都很正常,但问题在于他复杂度不对:

1
int Get(int x){ while(S[x].F) x = S[x].F ; return x ; }

这显然是个上界为$O(n)$的函数……不寒而栗……

所以他是不对的,这组数据可以很好的卡掉(由巨佬小粉兔制作)。

所以应该用一个并查集维护。而我们在路径压缩之后,必须要在 $pop$ 后,给 $pop$ 掉的点一个指针指向新的根,所以:

1
2
inline int Get(int x){ return S[x].rt == x ? x : S[x].rt = Get(S[x].rt) ; }
inline void Pop(int x){ S[x].val = -1, S[ls].rt = ls, S[rs].rt = rs, S[x].rt = Merge(ls, rs) ; }

于是最后的代码:

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
#include <cstdio>
#include <iostream>

#define MAXN 150010
#define swap my_swap
#define ls S[x].Son[0]
#define rs S[x].Son[1]

using namespace std ;
struct Tree{
int dis, val, Son[2], rt ;
}S[MAXN] ; int N, T, A, B, C, i ;

inline int Merge(int x, int y) ;
int my_swap(int &x, int &y){ x ^= y ^= x ^= y ;}
inline int Get(int x){ return S[x].rt == x ? x : S[x].rt = Get(S[x].rt) ; }
inline void Pop(int x){ S[x].val = -1, S[ls].rt = ls, S[rs].rt = rs, S[x].rt = Merge(ls, rs) ; }
inline int Merge(int x, int y){
if (!x || !y) return x + y ; if (S[x].val > S[y].val || (S[x].val == S[y].val && x > y)) swap(x, y) ;
rs = Merge(rs, y) ; if (S[ls].dis < S[rs].dis) swap(ls, rs) ; S[ls].rt = S[rs].rt = S[x].rt = x, S[x].dis = S[rs].dis + 1 ; return x ;
}
int main(){
cin >> N >> T ; S[0].dis = -1 ;
for (i = 1 ; i <= N ; ++ i)
S[i].rt = i, scanf("%d", &S[i].val) ;
for (i = 1 ; i <= T ; ++ i){
scanf("%d%d", &A, &B) ;
if (A == 1){
scanf("%d", &C) ;
if (S[B].val == -1 || S[C].val == -1) continue ;
int f1 = Get(B), f2 = Get(C) ; if (f1 != f2) S[f1].rt = S[f2].rt = Merge(f1, f2) ;
}
else {
if(S[B].val == -1) printf("-1\n") ;
else printf("%d\n", S[Get(B)].val), Pop(Get(B)) ;
}
}
return 0 ;
}

一道水题

无论怎么说,单独用一篇博客来整理板子题实在是太 Low 了(尤其是显得笔者很没品位),于是就直接拼到一起吧qwq

[LuoguP1456]Monkey King 链接

这玩意儿真tm水爆啊…直接存个代码证明我做过这道题吧qaq:

等会儿,突然想起来这道题的坑点来。就是原来的板子题,都是维护序列那种感觉,一个元素 pop 掉之后又就不用管它了。但是这道题是一道应用题,所以不应该删完不管,应该清空 qwq。

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
#include <cstdio>
#include <cstring>
#include <iostream>

#define MAXN 200010
#define lc T[x].Son[0]
#define rc T[x].Son[1]
#define rep(a, i, b) for(i = a ; i <= b ; ++ i)

using namespace std ;
struct Heap{
int val, dis, Son[2], rt ;
}T[MAXN] ; int N, M, A, B, i ;

inline int get(int x){
if (x == T[x].rt) return x ;
return T[x].rt = get(T[x].rt) ;
}
inline int Merge(int x, int y){
if (!x || !y) return x + y ;
if (T[x].val < T[y].val) x ^= y ^= x ^= y ;
rc = Merge(rc, y) ; if (T[lc].dis < T[rc].dis) lc ^= rc ^= lc ^= rc ;
T[lc].rt = T[rc].rt = T[x].rt = x, T[x].dis = T[rc].dis + 1 ; return x ;
}
int main(){
while (~scanf("%d", &N)){
memset(T, 0, sizeof(T)) ;
rep(1, i, N) T[i].rt = i, scanf("%d", &T[i].val) ; cin >> M ;
rep(1, i, M){
scanf("%d%d", &A, &B) ; int rt1, rt2 ;
int f1 = get(A), f2 = get(B) ; int ff1, ff2 ;
if (f1 == f2) { puts("-1") ; continue ; }
T[f1].val >>= 1, T[f2].val >>= 1 ;
rt1 = Merge(T[f1].Son[0], T[f1].Son[1]) ;
T[f1].Son[0] = T[f1].Son[1] = T[f1].dis = 0 ;
rt2 = Merge(T[f2].Son[0], T[f2].Son[1]) ;
T[f2].Son[0] = T[f2].Son[1] = T[f2].dis = 0 ;
ff1 = Merge(f1, rt1), ff2 = Merge(f2, rt2) ;
T[ff2].rt = T[ff1].rt = Merge(ff1, ff2) ;
printf("%d\n", T[get(T[ff1].rt)].val) ;
}
}
return 0 ;
}

upd: 2020.4.15 重写了一遍,觉得还是这个码风看着比较顺眼。

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
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std ;

const int N = 200010 ;

namespace Ltree{
#define rt(x) s[x].rt
#define lc(x) s[x].lc
#define rc(x) s[x].rc
#define ds(x) s[x].dis
#define val(x) s[x].val
struct Tree{
int rt ;
int lc ;
int rc ;
int val ;
int dis ;
}s[N] ;
int find(int x){
if (x == rt(x)) return x ;
return rt(x) = find(rt(x)) ;
}
int merge(int x, int y){
if (!x || !y) return x + y ;
if (val(x) > val(y)) swap(x, y) ;
rc(x) = merge(rc(x), y) ;
if (ds(lc(x)) < ds(rc(x))) swap(lc(x), rc(x)) ;
rt(lc(x)) = rt(rc(x)) = rt(x) = x ;
ds(x) = ds(rc(x)) + 1 ;
return x ;
}
void pop(int x){
val(x) = -1 ;
rt(lc(x)) = lc(x) ;
rt(rc(x)) = rc(x) ;
rt(x) = merge(lc(x), rc(x)) ;
}
}
using namespace Ltree ;
int n, m ;

int main(){
ios::sync_with_stdio(0) ;
cin.tie(0) ; cout.tie(0) ;
cin >> n >> m ; int k, x, y ;
for (int i = 1 ; i <= n ; ++ i)
cin >> s[s[i].rt = i].val, s[i].lc = s[i].rc = 0 ;
while (m --){
cin >> k >> x ;
if (k == 2) {
int ans = val(find(x)) ;
//cout << val(4) << '\n' ;
if (val(x) < 0) cout << "-1" << '\n' ;
else cout << ans << '\n', pop(find(x)) ;
}
else {
cin >> y ; int fx, fy ;
if (!(~val(y))) continue ;
if (!(~val(x))) continue ;
fx = find(x), fy = find(y) ;
if (fx != fy) rt(fx) = rt(fy) = merge(fx, fy) ;
}
}
return 0 ;
}