平衡树

UPD 02.15:更新了区间操作部分。

约莫半月前练习专题时,发现几道解法多样的题目,其中需要运用一些中高级数据结构。苦于之前没有学习过平衡树,便挑选了一种易于上手、实现简单的平衡树学习,也即FHQ Treap。由11年国家队队员范浩强发明。

为书写方便,文章中可能将直接使用pp代指某节点的随机权值,val\text{val}代指节点关键码(即记录的数值),hh代指树高,siz\text{siz}代指子树大小,cnt\text{cnt}代指节点副本数(相同关键码的节点),rt\text{rt}存储根节点编号。

(更多…)

More
  • 2022年2月15日