暗黙的なキー+スペース圧縮によるデカルトツリー

この記事を読む前に、暗示的なキーによってデカルトツリーが何であるかを理解する必要があります（これは複数の記事のトピックなので、 ここで読むことをお勧めします ）。 スペース圧縮は、データを圧縮するために使用される方法です。 たとえば、セット{1、1、1、2、2、2、2、3、1、1}を保存する代わりに、{1 x 3、2 x 3、3 x 1、1 x 2}を保存します。
次に、この方法を使用してスペースを圧縮し、任意のセグメントでオンライン操作を実行できるようにします。

そのようなツリーの実装をすぐに提供します

struct treap_node { int x, y; treap_node *l, *r, *p; int width; int val; //    void push() { //       } //  ,     void update() { x = width; if (l) x += l -> x; if (r) x += r -> x; if (l) l -> p = this; if (r) r -> p = this; //   ,    ,      } treap_node(int _width, int _val) { //   // val -  , width -    y = (rand() << 16) + rand(); l = r = p = NULL; width = _width; val = _val; update(); } }; //  2  treap_node* merge(treap_node *l, treap_node *r) { if (l == NULL) return r; if (r == NULL) return l; if (l -> y >= r -> y) { l -> push(); l -> r = merge(l -> r, r); l -> update(); return l; } else { r -> push(); r -> l = merge(l, r -> l); r -> update(); return r; } } //  1   2 void split(treap_node *t, int x, treap_node *&l, treap_node *&r) { if (t == NULL) { l = r = NULL; return; } t -> push(); if ((t -> l == NULL ? 0 : t -> l -> x) >= x) { split(t -> l, x, l, t -> l); if (l != NULL) l -> p = NULL; t -> update(); r = t; return; } else if ((t -> l == NULL ? 0 : t -> l -> x) + t -> width <= x) { split(t -> r, x - (t -> l == NULL ? 0 : t -> l -> x) - t -> width, t -> r, r); if (r != NULL) r -> p = NULL; t -> update(); l = t; return; } else { //   .       ,      treap_node *t1 = new treap_node(x - (t -> l == NULL ? 0 : t -> l -> x), t -> val); treap_node *t2 = new treap_node(t -> width - t1 -> width, t -> val); l = merge(t -> l, t1); r = merge(t2, t -> r); l -> p = NULL; r -> p = NULL; delete(t); } } 

通常のデカルトツリーと比較して、widthプロパティが構造に表示されていることに注意してください。現在の頂点に格納されているセグメントの幅です。 そして、valは意味そのものです。
別の大きな変更-分割機能

 else { //   .       ,      treap_node *t1 = new treap_node(x - (t -> l == NULL ? 0 : t -> l -> x), t -> val); treap_node *t2 = new treap_node(t -> width - t1 -> width, t -> val); l = merge(t -> l, t1); r = merge(t2, t -> r); l -> p = NULL; r -> p = NULL; delete(t); } 

ifの別の部分を次に示します。 これは、セグメントを2つのサブセグメントに分割することを指します。 そして、左右に接着します。

私がこれを使用する問題では、漸近的な動作に影響しないため、マージ関数は変更しません。 このようにして、スペース圧縮の問題を解決し、オンラインでリクエストに応答できます。 原則として、誰かがそれを必要とする場合、関数mergeを書き換えて2つのセグメントを結合することもできます。 すべての可能なデータを読み取り、固定セグメントを指定してから、binpo検索を使用して必要なセグメント数を検索し、セグメントツリーで必要な変更を行う代わりに、同じ漸近線に対して、小さなifで管理します。 確かに、デカルトツリーを使用する必要があります。 私にとっては、これを書くほうがはるかに便利で高速です。 たぶんこれは誰かに役立つでしょう。