不用旋转的treap?——fhq treap

前置知识:二叉排序树treap(https://www.luogu.org/blog/ztz11/pinghengshu-bst)了解什么是函数式编程(https://www.sohu.com/a/222320820_355140)本文代码均未经编译,如有错误请指出。826755370-“平衡树好烦啊,转来转去的,而且treap遇到区间序列问题就gg。

有两种类型的划分,一种是权重划分,另一种是划分。我们来谈谈权力的分裂。如图所示,当我们遍历一个节点时,如果它的权重小于k,那么它的左子树将被分割成左边的树,然后我们将迭代它的右子,如果它大于k,然后把它右边的子树分配给右边的树。如果我现在达到递归边界==0怎么办?这里有两种情况:1.root=0(即第一次分割),很明显初始化x和y,即x=y=0。

排名分割类似于权重的分割,将第一个k放在一个树中,其余放在另一个树中。码:

如图所示,我们假设第一棵树的权重小于第二棵树的权重,然后我们比较它们的随机权重。如果rnd[l]=rnd[r],那么我们可以保留第二棵树的右子树,另一棵树作为左子树。码:

完成上述操作后,我们可以使用函数式编程的思想来完成剩余的操作。直接暴力合并,代码:

要删除权重值为v的点,首先将整个树以v作为权重分割为两个树a,b,然后根据v-1将树分成c,d。这时,v的值必须是d的根,然后我们将合并d的两个儿子(关键点:这一步是为了消除v的影响),然后重新合并它们以得到一棵新树,这个树删除了v。代码的效果:

根据a-1的权重直接分离树木,然后x树中最大的树木应小于或等于a-1,则a的等级为大小[x]+1。码:

不想说什么,直接看一下代码:让我们先看看前一个,因为它小于a,所以我们仍然按照a-1的权重划分x,现在x中的最大数字必须小于或等于a-1,所以我们直接输出x最大的数字是好的,继承不会重复。码:

查询间隔[l,r]将树分割成三棵树,检查中间树,然后将它们合并。码:

Fhqtreap可以持久化。如图所示,每次拆分和合并时,都可以创建一个新的。请注意,下游标记还必须创建一个新点。1.LuoguP3369普通迪斯科平衡树(https://www.luogu.org/problemnew/show/P3369)是为了整合上述东西。码:

持久性序列需要三个操作:1lr,将间隔从l翻转到r;2lr,询问从l到r的间隔;3p,返回p。每次修改新点以翻转标记时,代码(感谢permui的代码http://www.cnblogs.com/owenyu/):

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180908A0J5JO00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券