心血来潮学习了FHQ Treap
代码量挺短的

首先肯定要挂上dalao原文远航之曲

FHQ Treap相比于普通Treap
一个特性就是没有旋转
通过两个操作splitmerge
来维护二叉搜索树和堆的性质

1.split 分裂

一种是按照权值分裂
split(now,k,x,y)
表示以k为条件分成xy两颗子树
就是把所有<=k的值放在x里面
然后>k的值放在y里面
如果一个节点的值小于等于k,就把他的左儿子全部扔到第一颗树里面,分裂右儿子
如果一个节点的值大于k,就把他的右儿子全部扔到第二颗树里面,分裂左儿子

 

另一种前K个版
比较类似,每次将K的值减去sz

 

2.merge 合并

merge(x,y)
合并的要求是val[x]<=val[y]
然后根据维护堆的性质
rnd[x]< rnd[y]
y和x的右子树合并
rnd[x]>= rnd[y]
x和y的左子树合并
记得维护sz

 

然后那些各种操作版子有写

 

然后是splay的经典题,区间翻转

分类: 数据结构算法

1
说点什么

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
DefFrancis Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒