（今天本想讲LCT 但本人TCL 所以大概率讲完会的还是会 不会的还是不会 所以将点简单的 巨神们可以去切题了）
引入
想必大家都已经十分熟悉二叉搜索树了 它是很好用的数据结构 但二叉搜索树仍存在问题 即当插入数据单调时 搜索树退化成一条链
这时我们使用一种称为平衡树的数据结构来优化它
想必大家也已经从那名为ZYX的存在对那AVL的神圣解释中对此十分熟悉啦
带大家复习一下伸展树
功能
伸展树作为一种平衡树其时间复杂度并不优秀 但因应用多样而在算法竞赛中广泛使用 较为重要
支持二叉搜索树全部功能 并因可以无损变换树形结构 是实现动态树（LCT）的基础
整个过程源于二叉搜索树的实际应用特点：当访问一个数据后大概率还会很快再次访问此数据 所以可以当每次对数据一个操作后 将其旋转到根
但这样的特点并不普遍（比如毒瘤出题人的毒瘤数据）
不过在将其旋转到根的过程中 可以实现一平衡操作 即得splay
实现
核心是splay操作 即将一点旋转到根
splay操作由rotate操作恰当组合而成
rotate操作即将一节点与其父子关系反向且仍保持二叉查找树性质
也就是一般常说的单旋操作
（让我现场画图qwq）
splay由双rotate旋组成
如果一节点的父亲与其父亲的父亲在一条直线上 则先rotate其父亲 再rotate其自身
否则两次rotate其自身
为什么要这样呢qwq
显而易见
(让我画个图解释一下)
其余操作非核心 边逐行大声朗读代码边说
例题P3369普通平衡树https://www.luogu.com.cn/problem/P3369
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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
| #include<iostream>
using namespace std;
int siz[100001],ch[100001][2];
int fa[100001],cnt[100001]
,val[100001];
int root=0,N,tot=0;
void pushup(int x)
{
siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+cnt[x];
}
int son(int x)
{
if(x==ch[fa[x]][0]) return 0;
else return 1;
}
void rotate(int x)
{
int y=fa[x];
int zch=ch[x][!son(x)];
int gr=fa[y];
bool yy=son(y),xx=son(x);
ch[gr][yy]=x;fa[x]=gr;
ch[x][!xx]=y;fa[y]=x;
ch[y][xx]=zch;fa[zch]=y;
pushup(y);pushup(x);
}
int splay(int x,int y)
{
while(fa[x]!=y)
{
int fat=fa[x];
int z=fa[fat];
if(z==y)
rotate(x);
else if(son(fat)==son(x))
{
rotate(fat);
rotate(x);
}
else
{
rotate(x);
rotate(x);
}
}
if(y==0) root=x;
}
void insert(int x)
{
int u=root,ff=0;
while(u&&val[u]!=x)
{
ff=u;
u=ch[u][x>val[u]];
}
if(u) cnt[u]++;
else
{
u=++tot;
if(ff)
ch[ff][x>val[ff]]=u;
ch[tot][0]=0;
ch[tot][1]=0;
fa[tot]=ff; val[tot]=x;
cnt[tot]=1;
}
splay(u,0);
}
void find(int x)
{
int u=root;
if(!u) return;
while(ch[u][x>val[u]]&&x!=val[u])
u=ch[u][x>val[u]];
splay(u,0);
}
int next(int x,int f)
{
find(x);
int u=root;
if(val[u]>x&&f||val[u]<x&&!f) return u;
u=ch[u][f];
while(ch[u][f^1]) u=ch[u][f^1];
return u;
}
void delet(int x)
{
int llast=next(x,0);
int nnext=next(x,1);
splay(llast,0);
splay(nnext,llast);
int del=ch[nnext][0];
if(cnt[del]>1)
cnt[del]--,splay(del,0);
else ch[nnext][0]=0;
}
int kth(int x)
{
int u=root;
if(siz[u]<x) return 0;
while(1)
{
int y=ch[u][0];
if(x>siz[y]+cnt[u])
{
x-=siz[y]+cnt[u];
u=ch[u][1];
}
else
if(siz[y]>=x)
u=y;
else
return val[u];
}
}
int main()
{
insert(-2147483647);
insert(2147483647);
cin>>N;
while(N--)
{
int opt;
cin>>opt;
if(opt==1)
{
int ppp;
cin>>ppp;
insert(ppp);
}
else
if(opt==2)
{
int ppp;
cin>>ppp;
delet(ppp);
}
else
if(opt==3)
{
int ppp;
cin>>ppp;
find(ppp);
cout<<siz[ch[root][0]]<<endl;
}
else
if(opt==4)
{
int ppp;
cin>>ppp;
cout<<kth(ppp+1)<<endl;
}
else
if(opt==5)
{
int ppp;
cin>>ppp;
cout<<val[next(ppp,0)]<<endl;
}
else
if(opt==6)
{
int ppp;
cin>>ppp;
cout<<val[next(ppp,1)]<<endl;
}
}
return 0;
}
|
文艺平衡树
思路:1.提取区间
2.打tag翻转
（让我画个图qwqwqw）
$T_n=k*T_{n-1}+n$
