【OI之路】02数据结构-3伸展树

6.4.1 定义

伸展树是一种相当灵活的平衡树结构
(灵活:便于添加和删除)
比较少直接使用,能应用于LCT

6.4.2 模版题

我把最重要的讲解放在这里面了
【Caioj1130】【Codevs4543】【Bzoj3224】普通平衡树

6.4.5 练习

Codevs3303文艺平衡树
Bzoj3196二逼平衡树
Bzoj1500维修数列

6.4.5 其他题目

Caioj1131 Bzoj1588 Codevs1296 HNOI2002 HNOI2014 营业额统计
Caioj1132 Bzoj1503 Codevs1286 NOI2004 郁闷的出纳员
Caioj1133 Bzoj1208 CCodevs1285 HNOI2004 宠物收养所
Caioj1137 Bzoj1058 Codevs1429 ZJOI2007 报表统计

6.4.6 总结

重点是利用伸展树的灵活性
另外,每次Splay既是加速也是重要的更新(pushdown/pushup)

如果还看不懂,阔以看看介个文章:
FlashHu

6.4.7 所有题目

Tag-伸展树

update

说说我对前驱后继操作的理解
我的写法是兼容【参数不存在】的情况的
findip会找到一个存在元素,可能不满足条件,但一定是在那个方向最接近的
(如果比d小,那么一定是其中最大的,反之亦然)
那么为了确保找到正确答案,不能直接找父亲什么的,要旋转到根,然后往那个方向按具体需求去找

目前已知的只有平衡树能实现,而set不能的功能:

  1. 找第k大等,与具体值没有关系,而且k不是首尾的操作(这里没必要用主席树)

目前已知的只有主席树能实现的东西:
区间第k大(如果像二逼平衡树那样树套树也行)

板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct Splay
{
struct Nod{int son[2],fa;}p[MAX_N];
int id;spt(){memset(p,0,sizeof p);id=0;}
bool son(int x) {return p[p[x].fa].son[1]==x;}
void rotate(int x)
{
int f=p[x].fa,ff=p[f].fa;p[ff].son[son(f)]=x;
int w=son(x),t=p[x].son[w^1];p[f].son[w]=t;p[x].son[w^1]=f;
p[x].fa=f;p[f].fa=x;p[t].fa=f;
}
bool isroot(int x) {return p[x].fa==0;}
int tmp[MAX_N];
void splay(int x,int rt)
{
for(int f=p[x].fa;!isroot(x);rotate(x),x=p[x].fa)
if(!isroot(y)) son(x)^son(y)?rotate(x):rotate(f);
}
}spt;

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/506a.html
转载请注明出处,谢谢!