如何证明FHQ-Treap这样分裂就是正确的
  • 板块灌水区
  • 楼主yutong_Seafloor
  • 当前回复4
  • 已保存回复4
  • 发布时间2024/1/9 18:53
  • 上次更新2024/1/9 22:01:04
查看原帖
如何证明FHQ-Treap这样分裂就是正确的
773747
yutong_Seafloor楼主2024/1/9 18:53

蒟蒻没想明白怎么寻找分裂结点,如何判断从这里分裂是正确的

日报上是这么说的:

为什么这样分裂是正确的?当我们对左区间树不断建立虚拟的右儿子时,而 now 的 val 都是单调不减的,所以左区间树满足二叉搜索树的性质,当我们对右区间树不断建立虚拟的左儿子时,而 now 的 val 都是单调不增的,所以右区间树满足二叉搜索树的性质。而这样建树又不会将祖先与后代的关系交换,即便祖父节点变成了父亲节点,它仍是祖先节点,所以左右区间树满足堆的性质。

出自:https://www.luogu.com.cn/blog/85514/fhq-treap-xue-xi-bi-ji

一点都看不懂,求大佬帮忙解释一下

bdfs P也不是

2024/1/9 18:53
加载中...