次に、この方法を使用してスペースを圧縮し、任意のセグメントでオンライン操作を実行できるようにします。
そのようなツリーの実装をすぐに提供します
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で管理します。 確かに、デカルトツリーを使用する必要があります。 私にとっては、これを書くほうがはるかに便利で高速です。 たぶんこれは誰かに役立つでしょう。