【BZOJ3224】普通平衡树 非旋转treap

以前这道题使用过替罪羊树、旋转版treap,还有splay(常数小王子),这次用非旋转的treap来做一下这道。

简单介绍一下非旋转treap的主要操作。其具有代表性的操作主要是两个:merge和split

Merge

merge是将两个treap合并。参数为两个子树根节点的编号a,b(有序)。其中要求a子树中的最大值小于等于b子树中的最小值。

在合并的时候,比较a,b节点的key值,这里以小根堆为例:

如果a的key较小,则将merge(a的右子树,b)作为a的右子树;否则将merge(a,b的左子树)作为b的左子树(注意顺序!)

然后递归下去,知道a和b中有一个为空,直接返回另一个,一遍返回一遍update。

Split

split是将一个treap(t0)拆成两个不相交的treap(t1,t2),拆后t1中的最大值小于等于t2中的最小值。

参数为t0,k,k表示从第几位开始分开。返回值为两个根节点编号,返回值童谣要求有序(用pair)

实现方式如下:

判断k是否和左子树大小相等,如果是直接分出左子树;判断是否和左子树大小+1相等,如果是,拆出右子树。

如果都不是的话,看k是否小于左子树大小,如果是,进入左子树split(s0,k);否则进入右子树split(s1,k-s1.size-1)。

递归做下去即可。另外可以加一条如果k是0直接返回,算是个小优化。

其他操作

其他操作大部分和普通的treap是一样的在这里不做赘述。

相似操作包括:

  • 查询排名 rank
  • 查询第k大 find
  • 查询前一个 pre
  • 查询后一个 nex

稍微不同一点的是插入和删除

  • 插入insert(v),直接rank找到不大于v的最大排名,然后按照rank split掉整棵树,然后新建一个节点储存v,与split出来的两个treap分别merge。
  • 删除del(k),要删除第k个,先split出前k个,再split出前k-1个,然后将前k-1个和k之后的部分merge。

大概就是这些了。

非旋转treap在代码量和效率上都不如普通的treap,但为什么还要写它呢?因为它支持可持久化,而旋转treap不支持(旋转会使父子关系结构被破坏),这使得非旋转的treap可以做到很多普通treap做不到的事情。至于可持久化的相关内容,我将会在之后的博客中阐述。

下面是代码XD:

题目链接

 

 

 

 

不如来评论一发?