分类:平衡树
平衡树(Treap)
惊!竟然没有Treap的博文!!
https://www.cnblogs.com/Thm-V/p/11297556.html
BZOJ1483 [HNOI2009] 梦幻布丁
链表+启发式合并
懒得写链表
std::set代替链表
首先算出初始状态答案
然后对于每个修改操作,启发式合并两种颜色。
启发式合并:在合并两个集合(或两棵树)时,暴力将较小集合的元素(或结点更少的树的所有节点)合并(或插入)到另一较大集合(或结点更多的树)中。
简单来说就是弱肉强食。
而且启发式合并的时间复杂度可以证明是O(logn)的
对于本题,枚举较小的集合的每个元素,处理答案并且加入较大的集合,同时更改颜色。
对于查询操作,由于每次修改同时都计算出答案,直接输出即可。
splay(平衡树)
【引入】
先来看一道题:营业额统计。
显然,对于每一天的营业额只要找出已有的营业额与其差值最小的就行了。那么便可以用二叉搜索树来实现这样的查找。
如果一棵二叉树如同下图,为一条链,那么每次查找的时间复杂度就和暴力没有什么差了。
我们可以发现,下图的二叉树与上图的二叉树是等价的,但下图的深度比上图的深度少了2,这样查找的时间复杂度也就减少了,那如何将上图的二叉树转化成下图的呢?splay便可以实现。
【思想】
【rotate】
这是原来的树。为了减小深度,我们把B结点旋转到根结点,那么A结点就成了B结点的儿子。由二叉树的性质我们可以知道B<E<A<C,那么可以得到如下的一棵新树。
rotate代码如下:
1
2
3
4
5
6
7
8
9
10
11 void Rotate(int x)
{
int fa = tree[x].fat, s = (x == tree[fa].son[1]), s1 = (fa == tree[tree[fa].fat].son[1]);
tree[tree[x].son[s^1]].fat = fa;
tree[fa].son[s] = tree[x].son[s^1];
if (tree[fa].fat)
tree[tree[fa].fat].son[s1] = x;
tree[x].fat = tree[fa].fat;
tree[x].son[s^1] = fa;
tree[fa].fat = x;
}
【splay】
splay则是rotate的拓展,因为对于一个点,只进行一次rotate显然并不会有多少优化,只有将其旋转至根结点才方便之后的操作。
splay的过程中需要分类讨论,如果是三点一线的话(x,x的父亲,x的祖父)需要先rotate x的父亲,否则需要先rotate x本身(否则会形成单旋使平衡树失衡)。
1
2
3
4
5
6
7
8
9
10 void splay(int x)
{
for (int y; (y = tree[x].fat) > 0;)
{
if (tree[y].fat)
Rotate((tree[tree[y].fat].son[1] == y)^(tree[y].son[1] == x) ? y : x);
Rotate(x);
}
root = x;
}
【insert/find/delete】
插入、查找、删除的操作于普通平衡树一样。只是在最后要将操作的点旋转到根结点。
插入:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 void ins(int va)
{
int x = root;
if (!tree[x].val)
{
tree[++tot].val = va;
tree[tot].tot = tot;
root = tot;
return ;
}
for (;tree[x].son[va > tree[x].val] && tree[x].val != va; x = tree[x].son[va > tree[x].val]);
if (tree[x].val == va)
{
tree[x].cnt++;
return ;
}
tree[++tot].val = va;
tree[tot].fat = x;
tree[x].son[va > tree[x].val] = tot;
splay(tot);
}
查找:
1
2
3
4
5
6 void Find(int va)
{
int x = root;
for (;tree[x].val != va; x = tree[x].son[va > tree[x].val]);
splay(x);
}
查找前驱/后继:
1
2
3
4
5
6
7 int Find_max(int x)
{
int y = tree[x].son[0];
for (;tree[y].son[1]; y = tree[y].son[1]);
splay(y)
return y;
}
删除:
删除的操作相对麻烦。如果其只有一个儿子,那么将它的儿子当作根结点就可以。否则,要先找出当前结点的前驱/后继,将其旋转到根结点。那么要操作的结点一定是根的一个儿子,并且它只有一个儿子,于是只要将根的儿子指向要操作的结点的儿子即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 void del(int x)
{
if (tree[x].cnt > 1)
{
tree[x].cnt--;
return ;
}
int l = (tree[x].son[0] != 0), r = (tree[x].son[1] != 0);
if (!l && !r)
{
root = 0;
return;
}
if (!l)
{
tree[tree[x].son[1]].fat = 0;
root = tree[x].son[1];
return ;
}
splay(Find_max(x));
tree[root].son[1] = tree[x].son[1];
if (r) tree[tree[x].son[1]].fat = root;
}
【总结】
splay是一种优化二叉查找的方法,所有的操作一定都满足二叉搜索树的性质。
完整代码:
[HNOI 2002] 营业额统计
题意:
给出每天的营业额,求出与之前营业额的最小差值加入答案。
很明显的平衡树,只要注意特殊情况和判重即可。
关于平衡树,可以看这史上最详尽的平衡树(splay)讲解与模板
其中代码都是非指针的。
继续阅读[HNOI 2002] 营业额统计
[Tyvj 1728] 普通平衡树
[HNOI2002] 营业额统计
Splay
BZOJ 题面不完整......简直没法做。
每天的最小波动值只可能由之前数值小于它的最大值与大于它的最小值更新而来。
对于每天的营业额用一个 Splay 查找其在树上的前驱与后继并计算答案,然后将其加入树中。
代码如下:
[Vijos 1291] 苹果摘陶陶
BZOJ3224 Tyvj1728 普通平衡树
本题可以使用平衡树,线段树,甚至std::vector通过。
splay的话直接做就可以了。
对于1操作,直接插,注意无需重复插入同一数字,用cnt数组统计数字出现次数即可。
对于2操作,先将要删的点splay至根节点,然后分4种情况。1.若根节点的cnt值大于1,将其-1;2.若根节点的cnt值等于1且无左右子节点,清空整棵树;3.若根节点的cnt值等于1且左右子节点无其中一个,将根结点一直另一子节点;4.若根节点的cnt值等于1且左右子节点都存在,找出根节点的前驱,将其splay至根节点,即可删除原来的根节点。注意在2,3,4情况时处理好父子节点的关系。
对于3,4,5,6操作,应用类似普通二叉查找树的方法即可。注意在5,6操作中可能存在查询不在树中的数字。
BZOJ1588 [HNOI2002]营业额统计
splay。
把每天的营业额加入splay,查找前驱和后继,统计即可。
注意使用双旋的splay,因为单旋在链状树的情况下时间复杂度会退化。具体证明去问Tarjan。
也可使用其他平衡树或双向链表。双向链表的做法可参考 朱晨光《基本数据结构在信息学竞赛中的应用》。