Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

平衡树

Posted on

$splay$ 应该不用讲吧，就写写 $fhq \ Treap$ 就可以了。

简介

可执行的操作

  • 分离（$split$）将一棵树分成两棵树。
  • 合并（$merge$）将两棵树合成一棵树。

split

  • 它的主要思想是将一个 $Treap$ 分成两个。
  • 这样的操作有两种类型：1.按权值来分。2.按前 $k$ 个来分。

权值版

1
2
3
4
5
6
7
8
9
void split(int now, int k, int &x, int &y)
{
    if (!now) x = y = 0;
    else {
        if (val[now] <= k) x = now, split(ch[now][1], k, ch[now][1], y);
        else y = now, split(ch[now][0], k, x, ch[now][0]);
        pushup(now);
    }
}

前k个

  • 其实这和 $Splay$ 的找 $k$ 大数差不多。
1
2
3
4
5
6
7
8
9
void split(int now, int k, int &x, int &y)
{
	if(!now) x = y = 0;
	else{
		if(val[now] <= k) x = now, split(ch[now][1], k, ch[now][1], y);
		else y = now, split(ch[now][0], k, x, ch[now][0]);
		pushup(now);
	}
}

merge

  • 将两个 $Treap$ 合成一个，保证第一个的权值小于第二个。
  • 满足大数一定在右边，小数一定在左边，但是因为是按随机权值插入，所以树的形状不固定（考试时 $TLE$ 了一定要申诉）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int merge(int x, int y)
{
	if(!x || !y) return x + y;
	if(pri[x] < pri[y])
	{
		ch[x][1] = merge(ch[x][1], y);
		pushup(x);
		return x;
	}
	else{
		ch[y][0] = merge(x, ch[y][0]);
		pushup(y);
		return y;
	}
}

拓展之后的操作

insert

  • 插入一个权值为 $v$ 的点，先把树按照 $v$ 的权值 $split$ 成两个，在按照顺序merge回去。
1
2
3
4
5
void insert(int v)
{
	split(root, v, x, y);
	root = merge(merge(x, make(v)), y);
}

remove

1
2
3
4
5
6
7
void remove(int v)
{
	split(root, v, x, z);
	split(x, v - 1, x, y);
	y = merge(ch[y][0], ch[y][1]);
	root = merge(merge(x, y), z);
}

near

  • 就是前驱后继
1
2
3
4
5
6
7
8
9
int near(int v, bool op) // op == 1 为前驱，反之即为后继 
{
	split(root, v - (op == 0), x, y);
	int k;
	if(op == 0) k = val[get_k(x, sz[x])];
	else  k = val[get_k(y, 1)];
	root = merge(x, y);
	return k;
}

例题：luoguP3369 【模板】普通平衡树

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
#include<bits/stdc++.h>
using namespace std;
const int N = 100001;
template <class T>
inline void read(T &res)
{
	res = 0; bool flag = 0;
	char c = getchar();
	while(c < '0' || c > '9'){if(c == '-') flag = 1; c = getchar();}
	while('0' <= c && c <= '9'){res = (res << 3) + (res << 1) + c - '0', c = getchar();}
	if(flag) res = -res;
}
int n;
int root;
int ch[N][3]; // 儿子
int val[N]; // 每个点的权值 
int pri[N]; // 随机生成的附件权值？ 
int sz[N]; // 以 i 为节点的树的节点的数量 
int tot; // 总节点数量
void pushup(int x)
{
	sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;
}
int make(int v)
{
	sz[++ tot] = 1, val[tot] = v, pri[tot] = rand();
	return tot;
}
int merge(int x, int y) // 合并 
{
	if(!x || !y) return x + y;
	if(pri[x] < pri[y])
	{
		ch[x][1] = merge(ch[x][1], y);
		pushup(x);
		return x;
	}
	else{
		ch[y][0] = merge(x, ch[y][0]);
		pushup(y);
		return y;
	}
}
void split(int now, int k, int &x, int &y)
{
	if(!now) x = y = 0;
	else{
		if(val[now] <= k) x = now, split(ch[now][1], k, ch[now][1], y);
		else y = now, split(ch[now][0], k, x, ch[now][0]);
		pushup(now);
	}
}
int get_k(int now, int k)
{
	while(true)
	{
		if(k <= sz[ch[now][0]]) now = ch[now][0];
		else if(k == sz[ch[now][0]] + 1) return now;
		else k -= sz[ch[now][0]] + 1, now = ch[now][1];
	}
	return -1;
}
namespace pol
{
	int x, y, z;
	void insert(int v)
	{
		split(root, v, x, y);
		root = merge(merge(x, make(v)), y);
	}
	void remove(int v)
	{
		split(root, v, x, z);
		split(x, v - 1, x, y);
		y = merge(ch[y][0], ch[y][1]);
		root = merge(merge(x, y), z);
	}
	int near(int v, bool op) // op == 1 为前驱，反之即为后继 
	{
		split(root, v - (op == 0), x, y);
		int k;
		if(op == 0) k = val[get_k(x, sz[x])];
		else  k = val[get_k(y, 1)];
		root = merge(x, y);
		return k;
	}
}

int main()
{
	srand((unsigned)time(NULL));
	read(n);
	for(int i = 1;i <= n;i ++)
	{
		int op, a;
		read(op), read(a);
		if(op == 1)
		{
			pol:: insert(a);
			continue;
		}
		if(op == 2)
		{
			pol:: remove(a);
			continue;
		}
		if(op == 3)
		{
			int x, y;
			split(root, a - 1, x, y);
			printf("%d\n", sz[x] + 1);
			root = merge(x, y);
			continue;
		}
		if(op == 4)
		{
			printf("%d\n", val[get_k(root, a)]);
			continue;
		}
		if(op == 5)
		{
			printf("%d\n", pol:: near(a, 0));
			continue;
		}
		if(op == 6)
		{
			printf("%d\n", pol:: near(a, 1));
		}
	}
	return 0;
}