平衡二分探索木とTreap

Treapは平衡二分探索木の一種であり、Treapの解説はどれも冒頭でそのように説明している。

が、競技プログラミングでは平衡二分探索木として使うより $O(\log N)$ で色々な操作ができる配列として使う方が多いようであり、諸々の解説もそちらに寄っていると感じる。

多くの人が参照している以下の解説では、p.31までは平衡二分探索木として説明してきたがp.32のinsertから配列的に使う時の実装になっている。

このため「これではvalでソートできないのでは？」「二分探索はどうやるか？」と大変混乱した。

Treapの実装。
上の解説では

insert/eraseを実装し、それを使ってmerge/splitを実装する方法(insert-eraseベース)
merge/splitを実装し、それを使ってinsert/eraseを実装する方法(merge-splitベース)
の2つが紹介されており、insert/splitベースがおすすめされていた。

Treapの呼び分け。

keyの順序に興味がある場合は平衡二分探索木、興味がない場合は平衡二分木と呼ぶ作法の紹介

個人的には前者を特に「平衡二分探索木」と呼び、主に後者を指す時に「平衡二分木」という言葉を使うようにしていますが、競プロerの中でも確かな呼び分けがされていないように思います。先ほどのスライドで紹介されているTreapの実装は後者で、この問題で必要なのも後者です。