Joeの精進記録

旧：競プロ練習記録

進化したImplicit Treapたち

はじめに

昨年のAdvent Calendarで書いた、Implicit Treapというとても有能なデータ構造があります。

xuzijian629.hatenablog.com

機能をもりもり盛り付けた平衡二分探索木で、セグ木でできるような操作が、配列の要素を反転したり削除したり挿入したりしながらできるデータ構造です。

去年のAdvent Calendarでは一応モノイドを乗せる抽象化をしたImplicit Treapの実装を公開したのですが、あれ以来いろいろ進化したので改めて公開します。記事後半にあるPrioritySumというのとPairQueryというやつが主に新しいです。

マクロ等を一切使っていないので特に衝突なく貼るだけで動くはずです。

プレーン

library2/implicit_treap.cpp at master · xuzijian629/library2 · GitHub

コードがかなり長いのでリンクで共有します。よくあるRMQ+RUQ, RSQ+RAQなどの組み合わせについては事前に定義済みなのでそのまま使えます。

けんしんのLazySegmentTreeとまったく同じ継承方法を採用しています。こっちも便利なので宣伝しておきます。

サンプルコード(抜粋)

MinUpdateQuery<int, int> hoge;
hoge.set_by_vector(vector<int>(n, (1LL << 31) - 1));

hoge.query(l, r);
hoge.update(l, r, x);

リファレンス

int size()

現時点でのサイズを返します。 O(1)

void insert(int pos, T0 x)

先頭からposの位置にxを挿入します。たとえばpos = 0なら先頭に挿入します。 O(\log n)

void update(int l, int r, T1 x)

[l, r)の半開区間にxを作用させます。 O(\log n)

T0 query(int l, int r)

[l, r)の半開区間について累積を求めます。 O(\log n)

int binary_search(int l, int r, T0 x, bool left = true)

[l, r)内のkでf0(tr[k], x) != xとなる最左/最右のものの位置を返し、存在しない場合は-1を返します。 O(\log n)

説明が非直感的かと思うので具体例で説明すると、累積用の演算がminの場合、[l, r)の範囲にあるx未満の最左/最右の要素の位置を返します。

void erase(int pos)

位置posの要素を削除します。 O(\log n)

void reverse(int l, int r)

区間[l, r)を反転します。 O(\log n)

void rotate(int l, int m, int r)

区間の[l, r)の先頭がmになるようにシフトさせます。std::rotateと同じ仕様です。 O(\log n)

T0 operator[](int k)

インデックスアクセスができます。 O(\log n)

void dump()

デバッグ用です。配列の中身をprintします。

PrioritySum

これを含め、以下のライブラリはImplicit Treap(プレーン)に依存するので、そちらも一緒に貼って使ってください。 library2/priority_sum.cpp at master · xuzijian629/library2 · GitHub

ネーミングはびーとくんのライブラリから拝借していますができることは微妙に違います。

以下の操作が O(\log n)でできます。

  • 要素の挿入
  • 要素の削除(最大/最小要素でなくてもいい)
  • 上位k個の累積(このkが固定だったらびーとくんのでいい。定数倍軽い)

リファレンス

void add(T a)

要素を追加。 O(\log n)

void erase_at(int k)

位置を指定して要素を削除。先頭の削除ならk = 0を指定。 O(\log n)

void erase_value(T a)

要素を指定して削除。aがすでにaddされていることが仮定されている。 O(\log n)

int size()

要素数を返す。 O(1)

T sum(int k)

先頭k要素の累積を返す。 O(\log n)

T operator[](int k)

インデックスアクセスができます。 O(\log n)

void dump()

デバッグ用です。配列の中身をprintします。

PairQuery

ネーミングは適当です。私事ですがこの名前のライブラリを何種類かもっているので(機能は違う)名前を変えたい…

library2/pair_query.cpp at master · xuzijian629/library2 · GitHub

以下の操作が O(\log n)でできます。

  • ペアを挿入
  • ペアの第一要素がx以下の要素全体に対し、その第二要素の累積を求める

リファレンス

void add(const pair<T0, T1> &a)

挿入します。 O(\log n)

T1 query(T0 x)

第一要素がxの要素とxより左側にある要素に対し第二要素の累積を返します。 O(\log n)

あとはpriority_sumと似たような機能もあります。

おわり

月1ぐらいの頻度で使える。けっこうすごい。