はじめに
とある勉強会（競技プログラミングとは関係ない集まり）で、Implicit Treapを紹介する発表をしました。せっかく頑張って資料を作ったので、それを生かして記事にしようと思いました。スライド画像を貼ったうえで、説明をその下に書いていくスタイルで記事を書いていきます。
Implicit Treapとは
出禁は冗談ですが、それくらいなんでもできるインパクトのあるデータ構造です。
平衡二分探索木は SQLite の一部で使われているらしいです（chatGPTが言ってました）。
単なる配列としても使えるし、std::setのように常にソートされた状態を保つような使い方もできます。そしてそれらに対する様々な処理がどれもこれも $O(\log N)$ です。
単なる配列として使う場合のすごいところは、途中追加・削除が $O(\log N)$ でできることです。リスト（双方向リスト）は途中追加・削除を $O(1)$ でできそうに見えますが、削除するデータにアクセスする（見つける）のに $O(N)$ の計算量がかかってしまうので $O(N)$ としています。また、実用ではあまり区間反転を必要とする場面がなさそうなのでスライドでは太字になっていませんが、区間反転も他のデータ構造ではなかなかできないすごいところです。
ソート状態をキープする使い方はstd::setやstd::multisetでもできますが、違いは $k$ 番目が取得できるところです。たまに使える問題が出てきて、X(Twitter)で「平衡二分探索木貼るだけ」というようなコメントがつぶやかれていたりします。私が初めて平衡二分探索木すごそうというのを知ったのはそれでした。
できること１で書いた「単なる配列」「ソートキープ」のどちらの使い方に対しても、区間に対する総積を取得したり、区間に対して操作を施して更新したりするというセグメント木・遅延伝搬セグメント木と同じことができます。ソートキープしたデータ集合の先頭 $k$ 個の和が欲しくなったりすることがときどきありますが、そんなときに便利です。
セグメント木でできることが全部できる、と書いたのは言いすぎかもしれません。左右反転とは相性の悪い演算がありそうです。可換でないとだめそう。
まず子の個数が2個以下かどうかで分類しています。2個以下が二分木です。
次に二分木を値の持ち方で分類しています。二分ヒープは「子の値≦親の値」という制約のものです。一方で今回大事なのは二分探索木の方で、こちらは「左の子孫の値≦親の値≦右の子孫の値」という制約のものです。この2つが紛らわしいので注意しましょう。
二分探索木では、子が1つのときもそれが左か右かの情報を持ちます。図では、42の子は右のみで70、さらにその子は左のみで56、という例になっています。
二分探索木を更に分類します。スライド下方のgoodとbadの図は、どちらもデータ数12個でどちらも二分探索木になっています。しかしgoodの方は高さ3で済んでいるのに対し、badの方は高さ8です。この後のスライドで説明しますが、木が高いといろいろと困ったことになるので、高くなりすぎないようにしたいです。そのような機能を持っているものを平衡二分探索木と呼びます。
高さを低く維持する方法には様々なものが提案されています。最初に提案されたのは1962年のAVL木です。赤黒木は高速動作しかつ最悪計算量が保証されているという特徴があり、C++のstd::setなどに採用されています。競技プログラミングでよく実装されているのはSplay木、Treap、RBSTあたりでしょうか。その中で今回はTreapを紹介します。
Treapに、ある機能を付けたものがImplicit Treapで、さらにセグメント木機能を付けたものが遅延伝搬反転可能Implicit Treap、という位置づけになります。といっても遅延伝搬反転可能Implicit Treapという名前は使われておらず、セグメント木機能付きのものもImplicit Treapと呼ばれています。
さて、ここまでで説明した内容だと、二分探索木に格納されたデータは勝手にソートされてしまいそうです。どうやってソートされていない配列を格納するのか疑問に思いませんか？私は長い間疑問でした。その方法については後ほど説明します。
二分探索木について
次に、二分探索木について少し詳しく説明します。
まず、二分探索木への3種類の操作を説明します。秋葉拓哉さんの素晴らしい解説スライドを引用させていただいて説明します。オリジナルのスライドはこちら：
まず検索です。図は10を検索する例です。まず根の7と比較します。10の方が大きいので、右の子孫にあると分かります。そこで右の子に移動します。右の子は15です。15と比較すると10の方が小さいので、左の子孫にあると分かります。そこで左の子に移動します。左の子は10なので、見つかりました。
木の高さの分だけ比較が必要で、木の高さは偏りが少ないなら $O(\log N)$ なので、検索の計算量も $O(\log N)$ です。
次はデータの挿入です。図は6を挿入する例です。検索のときと同様にして、比較しながら降りていきます。葉まで到達したら、そこに新しい葉として挿入します。この操作はこの後の説明でも出てくるので覚えておいてください。
最後に削除です。この操作はこの後の話には関係ないのでざっくりの説明で済ませます。図は15を削除する例ですが、15を取り除くとその下にぶら下がった子達が困るので、左の子孫の中の最大値を代わりに入れます。詳しくはスライド左下に書いたとおり、少々ややこしい場合分けがあります。
二分探索木の形状は、同じデータ集合に対してたくさんあり得ます。図の3つの二分探索木は、どれも上の12個のデータ集合を表しています。この自由度については、次のスライドのように考えるとイメージをとらえやすいかと思います。
手順①～③を繰り返すことで、図に示したように二分探索木が構築されます。手順①で選ぶデータを変えると異なる二分探索木になるので、同じデータ集合から多数構築できることが分かると思います。
同じデータ集合でも、最悪な構築をすると右側のように高さが $O(N)$ になってしまいます。すると検索や挿入などの各種操作の計算量も $O(N)$ になり、困ります。こうならないよう工夫したのが平衡二分探索木です。
Treapの紹介
平衡二分探索木には前述のとおりたくさんの種類があります。その中で、前述の「できること1, 2」を実現するのに向いているのはSplay木、Treap、RBSTの3つです。この3つは、配列の分割・結合を高速に実現できるのですが、それが「できること1, 2」の実現に必要であるためです。その中で、Treap、RBSTは定数倍も良いとされています。TreapとRBSTでは、Treapの方が若干定数倍で有利であるようです。
Treapの平衡戦略はとてもシンプルで、前述の手順①をランダム選択にする、というだけのものです。それだけで木の高さが期待 $O(\log N)$ になります。この理由はクイックソートと同じです。クイックソートも、ピボットをランダムで選び、それより小さいか大きいかでデータを二分する、という操作を繰り返します。これはTreapの手順と全く同じになっています。
再びしばらく秋葉さんのスライドを引用させていただいて、Treapの優先度の話と、Treapの挿入操作の説明をします。
平衡戦略を実現するため、各頂点にデータ（キー）だけでなく「優先度」という乱数値を持たせます。
そして、親子関係にある頂点どうしでは、親の優先度の方が必ず大きくなるようにします。優先度だけ見ると二分ヒープになるということです。
これは前述の手順①で選ぶデータを、「優先度最大のもの」とすることに相当します。優先度は乱数なので、結局手順①でランダム選択したことになっており、Treapの平衡戦略が実現できています。
また、優先度が付くことで、手順①で選ぶデータが1つに定まるので、木の形は確定します。挿入や削除などで形が変わるたびに、その唯一の形になるよう操作することになります。
次に、Treapの挿入・削除の方法を説明します。まず優先度を無視し、普通の二分探索木の挿入と同じ方法で挿入します。図のとおり葉として挿入されます。
次に、優先度の条件が満たされるまで上に移動していきます。上下に移動する方法は「回転」と呼ばれます。
回転の図解です。左右の順序をA, P, B, Q, Cの順に保ちつつ、PとQの上下を入れ替えることができています。
削除は挿入を反対回しにするだけでOKです。
配列として使う方法：Implicit Treap
先にも説明したとおり、普通にデータを二分探索木に入れるとソートされてしまいます。任意の配列を、順序を保ったままどうやって格納すればよいでしょうか？
図でvalueと書いてある配列を、左右の順序を保ったまま格納したいとします。例えば、valueに左から昇順になるような適当なkeyを付与して、(key,value)のペアを格納すれば、左右の順序を保てます。key1と2の間にデータを挿入したいときは、keyを1.5として挿入すればよさそうです。しかし、挿入を繰り返すと、keyの間隔が半減を繰り返し、精度が足りなくなってしまいます。
（以降のスライドの図では、優先度を省略します。データとは別に優先度も頂点に付与されていることに注意してください。）
そこで、付与するkeyを「現在自分より左にあるデータ数」、言い換えると「その時点での配列の添え字」とするのが解決策です。つまり、keyが固定ではなく、動的な値になるということです。比較が必要になるたびkeyを再計算するわけですが、確かにそれでもうまく動作します。keyを陽に持たないので、implicit keyと呼ばれます。そしてこの実装が入ったTreapをImplicit Treapと呼びます。
key自体は持ちませんが、keyを計算するために「自分を根とする部分木のサイズ」を常に持つようにします。左の図で、上側に書かれた緑の数字がそれです。
変化が起こったら更新して常に最新状態にします。左の図に対しデータを1つ挿入した様子が右の図です。黄色の頂点が挿入されたデータで、その祖先にあたる頂点全てを、根の方向に向かう順で更新します。管理の手間は $O(\log N)$ です。
keyの計算は、右へ降りるたびに「左の子に格納されている部分木サイズ」を加算していくことでできます。図は黄色のデータに対し、その左にあるデータ数を得る様子です。根から黄色のデータに向かっていきます。まず右に降ります。その際、根の左の子孫すべてと、根自体が、右に降りた時点で「左側にあることが確定するデータ」ですので、その個数をカウントします。これを繰り返します。左に降りた場合は、新たに左側にあることが確定するデータは1つもないので、何もしません。
以上で説明した仕組みにより、配列として扱えるようになったので、次は配列のマージ・分割について説明します。マージは、再帰で考えるととてもシンプルになります。スライド左側は木で表したマージの様子、右側は配列で表したマージの様子で、同じものを表しています。図はaの優先度がbの優先度より大きい例で、aが根になります。すると、aの左の子はAのみ、右の子は「Bと、C,b,Dをマージしたもの」…★ になります（右側の図で見ると分かりやすい）。★は、元よりもサイズの小さいマージ処理ですので、後は再帰的に処理できます。実装は右下のとおり、10行弱で済んでしまいます。
分割は、優先度を気にせず、単に左右に切断してポインタを張り直すだけでOKです。こちらも再帰でかなり短く書けます。
実は、マージと分割を作ると、それらを使って挿入と削除を実現できます。図のとおり、分割して追加したり取り除いたりするだけです。また、逆に挿入と削除を作ると、それらを使ってマージと分割を作ることもできます。どちらを選んでもよく、マージと分割を作る人が多いらしいです。
遅延伝搬セグメント木機能の付け方
最後に、遅延伝搬セグメント木と同じことができるようにする方法を説明します。
遅延伝搬セグメント木では、長さ2, 4, 8, … の固定区間に対して、区間値（合計、maxなど）や遅延情報を持っていました。Implicit Treapでは、各頂点に、「自分を根とする部分木に対応する区間」の区間値・遅延情報を持たせます。右の図で、黄色の頂点に対応する区間は下の配列の矢印で、その中の最大値が7なので、黄色の頂点の区間値として7が格納されています。
区間値、遅延情報は、各種操作のたびに更新します。遅延情報の更新は、「左の子、自分の値、右の子」の3方向に伝搬するイメージです。区間値の更新も「左の子、自分の値、右の子」の3方向を集約するイメージです。
図は区間値を更新する様子です。黄色のデータが挿入されたら、そこから根方向に向かって更新していきます。各頂点の区間値は、左の子の区間値と、自分の値と、右の子の区間値、の3つの値のmaxに更新されていきます。
こちらは遅延伝搬の様子です。黄色の値を参照したいとします。根に書いてある紫色の+3は、根に対応する区間（つまり配列全体）に+3する、という意味の遅延情報です。根から黄色の頂点に向かって降りていきます。まず、根から右に降りたいですが、遅延情報があるので伝搬させます。根の値は+3されて4になり、左右の子に遅延情報の+3が伝搬します（右上図）。次は左の子に降りますが、その前にまた遅延情報を伝搬させます（左下図）。これを繰り返して右下図になり、黄色の頂点に到達したので値7を取得できました。
これまでの説明で、挿入・削除・マージ・分割などの各種操作を施しても常に区間値・遅延情報などが正しい値になるようにできました。すると、任意区間の区間値取得はとても簡単にできます。スライドの図のように、欲しい区間の左右端で分割すれば、自動的に欲しい区間の根に区間値が計算されます！これだけです。
任意区間への更新処理も同様で、図のとおり左右を切り離して、根に遅延情報を適用するだけです。再びマージすれば自動的に遅延情報が伝搬していきます。
最後に、左右反転の仕方についてです。左右反転は遅延情報の一種として実現できます。伝搬させる際、単に左右の子に伝搬させるだけでなく、左右の子へのポインタを入れ替えればよいです。図の配列の様子を見ると、左右反転が実現できているのが分かりやすいでしょうか。この後さらに最後まで伝搬させた図を書いてみると、確かに左右反転できていることが分かると思います。
参考文献情報です。参考文献[1]は本記事でも引用させていただきました、感謝です。実装したくなったら参考文献[2]を見るとよいです。