treapと呼ばれるデータ構造があります。これはランダム化されたバイナリ検索ツリーであり、ランダムに生成されたいわゆる「優先度」のヒープでもあります。
この構造にはさまざまなバリエーションがあり、キーは暗黙的であり、ツリーには保存されませんが、ツリー内のノードの順序付きインデックスをこのノードのキーと見なします。キーではなく、各ノードにサブツリーのサイズを保存する必要があります。この手法により、O（log N）時間で多くの操作（挿入、削除、サブ配列の復帰、間隔の変更など）をサポートする、ある種の配列のようなtreapについて考えることができます。
私はこの構造について少し知っていますが、それほど多くはありません。グーグルで検索してみましたが、treap自体に関する記事はたくさん見つかりましたが、この「暗黙のtreap」/「インデックス付きリスト」については何も見つかりませんでした。私の母国語は英語ではなく、聞いた講義では英語の元の用語ではなく、構造のネイティブ用語を使用していたため、その名前すらわかりません。このネイティブ用語は、英語で「暗黙のキーを処理する」または「暗黙のキーのデカルトツリー」として直接翻訳できます。
誰かがこの構造に関する記事を私に指摘したり、元の名前を教えてもらえますか？ありがとうございました。
PS私の英語が十分に理解できなかったらごめんなさい。
UPD：私が探している構造についてのいくつかの追加の説明。
ツリーに保存されている実際のユーザーデータである、ランダムに選択された優先度とキーを使用した通常のtreapについて考えてみます。次に、他のユーザー情報がすべてのノードに保存されており、キーは検索キーに他ならないことを想像してみてください。次のステップは、各ノードのサブツリーサイズを計算して維持することです。マージ/分割/追加/削除のたびにこのパラメーターを更新する必要がありますが、たとえば、O（log N）でツリーのK番目の要素を見つけることができます。時間。
各ノードにサブツリーサイズがある場合、キーを破棄して、treapが順序どおりにトラバーサルされたユーザーデータの配列を表すと想像できます。各要素の配列インデックスは、サブツリーのサイズから簡単に計算できます。これで、配列の途中で要素を追加/削除したり、この配列を分割したりできます-すべてO（log N）時間で。
「複数」の操作を行うこともできます。たとえば、「配列」のすべての要素に定数値を追加します。これを実装するには、この操作を遅延させ、遅延定数を表すパラメーターをすべてのノードに追加する必要があります。このパラメーターは、このノードのサブアレイのすべての要素に「後で」追加する必要があり、変更を次のように「プッシュ」します。必要。サブアレイに定数を追加したり、サブアレイをペイント（マーキング）したりすると、サブアレイを反転する（ここでは、ビット「サブアレイを反転する必要があります」のノードの遅延情報）などのように、サブアレイを遅延させることができます。
UPD2：これがコードスニペットです-私が見つけた少量の情報の一部です。キリル文字に気付かないでください:)「снеявнымключом」という言葉は、直訳で「暗黙の鍵を使って」を意味します。