std::setを使わない代替テクニック

競技プログラミングでは、C++ に std::set という（事実上）平衡二分探索木ライブラリがあるから、たまにその使用を前提とした問題が出る。

std::set, multiset は、集合を順序を持って管理するデータ構造であり、以下のことができる（set - cpprefjp C++日本語リファレンス より一部抜粋）

Pythonでは標準ライブラリにないし、実装してもリストアクセスの遅さからTLEに直面することがままある。

いや、実際には、別に使わなくても何とか別の方法がある場合が多いが、std::setが「使えば一発」なのに対し、問題依存の考察や実装の手間を要するのが常である。 （素直にC++で書けって？そりゃそうだ）

std::setを使いたいけど使えない……という場合に、代わりになりうる方法をメモ。

問題に出くわすごとに列挙していき、ある程度蓄積されたら分類方法を考える。

• Binary Indexed Tree
  • 汎用性の高い代替方法
• 優先度付きキュー (heapq)
  • 一定の制約の上で簡単&高速
• 問題依存の上手い方法
  • 列挙していけば何か共通点みたいなのが見つかるかも知れない
• C++コードを埋め込んで外部モジュールとしてコンパイル
  • [Python]平衡二分木が必要な時に代わりに何とかする変なテク[競プロ] - 菜
  • snippet/wrap_cpp_set.py at master · Lgeu/snippet · GitHub
• 要素アクセスを減らしてPythonでも高速に動く平衡二分木（ピボット木）を使う
  • 平衡二分木を実装する - Qiita
• 平方分割で管理する
  • GitHub - tatyam-prime/SortedSet

• 参考
  • k 番目の値を高速に取り出せるデータ構造のまとめ - BIT上二分探索や平衡二分探索木など - Qiita
  • 【Python】平衡二分木が必要な時に代わりに何とかするテク【競プロ】 - Qiita

汎用性の高い置き換え。

• 制約
  • 値は整数限定で、取り得る範囲は $1～10^6$（配列を作れる）程度

• できること
  • 値の追加・削除 $O(\log{N})$
  • $k$ 番目の値を求める $O(\log{N})$
  • $x$ が存在するか検索 $O(\log{N})$
  • $x$ より小さい・大きい直近の値を検索 $O(\log{N})$

Binary Indexed Tree で管理できる。ただし、BIT上で累積和の二分探索を実装する必要がある。 詳細はBinary Indexed Tree（Fenwick Tree）参照。

以下のように置きかえる。

• 値 $x$ を追加 → $bit.add(x, 1)$
• 値 $x$ を削除 → $bit.add(x, -1)$
• $k$ 番目の値を取得 → $bit.lower\_bound(k)$（累積和が $k$ 以上になる最小のindexを取得）
• $x$ の検索 → $bit.sum(x)-bit.sum(x-1) \gt 0$
• $x$ 以下の最大の値を取得 $bit.lower\_bound(bit.sum(x))$
• $x$ 以上の最小の値を取得 $bit.lower\_bound(bit.sum(x - 1) + 1)$

$x$ 以下の最大の値が存在しない場合、$1$ が返る。
$x$ 以上の最小の値が存在しない場合、$N+1$ が返る。
（※BITを1-indexedで実装していた場合。lower_boundの実装内容にも依るが）

そのような操作が発生しうる場合、indexをずらして、$i=1$ は空白要素として $i=2$ から本来の値を入れる、などで本当の値と区別できる。

          累積和               std::set
初期状態   1 2 3 4 5 6 7 8
          [0 0 0 0 0 0 0 0]    {}

5を追加
          [0 0 0 0 1 1 1 1]    {5}
3を追加
          [0 0 1 1 2 2 2 2]    {3, 5}

小さい方から2番目を取得
          [0 0 1 1 2 2 2 2]    {3, 5}
                   ^                            累積和で"2"が始まるiは「5」

2,3,7を追加
          [0 1 3 3 4 4 5 5]    {2, 3, 3, 5, 7}

4以下の最大の値を取得
          [0 1 3 3 4 4 5 5]    {2, 3, 3, 5, 7}
                 ~                              累積和で 4 の箇所は"3"
               ^                                累積和で "3" が始まるiは「3」

6以上の最小の値を取得
          [0 1 3 3 4 4 5 5]    {2, 3, 3, 5, 7}
                   ~                            累積和で 6-1=5 の箇所は"4"
                       ^                        累積和で 4+1=5 が始まるiは「7」

7を削除
          [0 1 3 3 4 4 4 4]    {2, 3, 3, 5}

6以上の最小の値を取得
          [0 1 3 3 4 4 4 4]    {2, 3, 3, 5}
                           ^                    存在しない場合、N+1 が返る点には注意

値の取り得る種類数が $N=10^6$ 程度で、かつ先読みできる場合、前もって圧縮して $1～N$ に対応づければよい。

BIT上の二分探索では、累積和が $k$ 以上になる要素そのものは分かっても、前後の値はたどれない。

この方法では前後の値を求めたい場合は $k \pm 1$ で累積和の二分探索を改めて行うしかない（と思う）。

ただし、小さい方の値を求める際、以下の方法で少しだけ省略できる場合がある。

累積和の探索では、その過程で、累積和が $k$ 以上になる最小の要素を $x$ として「$x$ 未満の要素の個数」も求めることになる。 （これを $L[k]$ と表す）

• $L[k]=k-1$ なら、改めて累積和が $k-1$ 以上になる最小の要素を二分探索
• $L[k] \lt k-1$ なら、$x$

• 制約
  • $k$ 番目の値を取得する、というクエリの $k$ は固定
  • 検索はできない

• できること
  • 値の追加 $O(\log{N})$ （削除は一工夫必要、バリエーション参照）
  • $k$ 番目の値を取得 $O(1)$

2つの優先度付きキューを用いることで代替できる。

Binary Indexed Treeでは実現できない、$10^9$ など配列を作るのが厳しい範囲のクエリや、整数値以外にも対応できる。

• lower: 常に値の個数を $k$ 個に保つ優先度付きキュー。大きい方から取り出す
• upper: $k$ 個から溢れた分を管理する優先度付きキュー。小さい方から取り出す

答えは常にlowerの先頭に位置する（$x$ とする）。新しい値 $y$ が来たとき、

• $x \le y$ なら、$y$ をupperにpush
• $x \gt y$ なら、$x$ をlowerよりpopし、代わりに $y$ をpush。$x$ はupperにpush

lowerとupperの要素数が同じになるように保ちながら追加していく。

削除されるのが $k$ 番目の値に限定されるなら、つねに優先度キューの先頭にあるので可能。

優先度キューとは別に、「値が生き残っているか」を管理するデータを用意する。

• 要素に重複が無い場合
  • 「値:$x$ は生き残っているか」を管理するデータ
• 要素に重複がある場合
  • 要素にIDをつける
  • 「ID:$i$ は生き残っているか」を管理するデータ
• lowerで生き残っている要素数を管理する変数 $lc$（lowerの個数が $k$ 未満になる可能性のある場合）
• lower, upperで生き残っている要素数を管理する変数 $lc, uc$（中央値を求める場合）

値 $y$ を削除するとき、lowerの先頭 $x$ と比較して、

• $x \lt y$ なら、$y$ を削除済みにする
• $x \ge y$ なら、$y$ を削除済みにし、upperからlowerに1要素移す

popするとき、それが生き残っている値かどうかを確認し、削除済みなら無かったこととして続けてpopする。

一概には言えないけど、だいたい以下のような問題に適用できうる。

• 順列など、全ての要素が異なる配列を考える
• 各要素について、「自分の左(右)で自分に最も近い、自分より小さな(大きな)値の位置」を求めたい

Binary Indexed Tree でもいいんだけど、より高速で、なかなかアイデアが綺麗な解法。

これを使って解ける問題（ネタバレ注意）

std::setであれば、値の小さい順に「要素のindex」をinsertしていく方法が考えられる。

ある要素 $A_i$ を挿入しようとしたとき、既にset内にあるのは自身より小さな要素のindexに限られる。 そこから $i$ 未満で最も大きい数を検索すれば、それが $A_i$ にとって、自身より小さな左で直近の要素の位置である。

各要素の暫定解を表す配列を用意して、値の大きい順に処理して更新していく。

• $L$: 自身より左で、自身より小さい直近の要素のindex（暫定）
• $R$: 自身より右で、自身より小さい直近の要素のindex（暫定）

ある要素の処理が終わったら、後から処理される要素のために、自身をスキップさせるよう更新する。

横一列に繋がったグラフの辺を繋ぎなおすと考えるとわかりやすい。

【初期状態】
i   1   2   3   4   5   6
   ③--①--④--⑥--⑤--②
L   0   1   2   3   4   5    自身より左で自身より小さい要素の i （暫定）
R   2   3   4   5   6   7    自身より右で自身より小さい要素の i （暫定）

はじめはすぐ左・すぐ右の位置を入れておく

【最も大きい要素⑥】
処理された時点のL,Rの値がそのまま答えとなる。
最初はどの要素も自分より小さいので、すぐ左・すぐ右のindexとなるのは当然。
i   1   2   3   4   5   6
   ③--①--④--⑥--⑤--②
L   0   1   2  [3]  4   5
R   2   3   4  [5]  6   7

次の処理のために、⑥を抜いて、④と⑤を直結させたい。
i   1   2   3   4   5   6
   ③--①--④------⑤--②
L   0   1   2       _   5
R   2   3   _       6   7

そのためには、以下のように更新すればよい
L[R[i]] = L[i]
R[L[i]] = R[i]

今回に当てはめると、
L[5] = 3
L[3] = 5

i   1   2   3   4   5   6
   ③--①--④------⑤--②
L   0   1   2      [3]  5
R   2   3  [5]      6   7

【2番目に大きい要素⑤】
同様に、この時点での L[i]=3, R[i]=6 が⑤にとっての答え
i   1   2   3   4   5   6
   ③--①--④------⑤--②
L   0   1   2      [3]  5
R   2   3   5      [6]  7

同様に更新すると、ちゃんと④と②がつながる
i   1   2   3   4   5   6
   ③--①--④----------②
L   0   1   2          [3]
R   2   3  [6]          7

これを繰り返すと、$O(N)$ で求められる。std::setを使うと $O(N\log{N})$ なので、それより高速である。

値が飛び飛びなら、先読みできるなら圧縮すればよい。先読みできない場合は……わからん。

同じ値が含まれると、同率の処理が上手くいかない。

一応、自身の値 “以下” の直近の位置を求めればいいなら、方法がある。

• $L[i],R[i]$ の取得を同率の要素ごとにまとめて行い、更新は全ての同率の要素が終わった後で一括に行う

自身の値 “未満” なら……どうやればいいだろうね。

• はじめ $1～N$ の整数が1つずつ入った集合がある
• 以下の2つのクエリを処理する
  • 1. 整数 $i$ を集合から取り除く
  • 2. 現在、$i$ 以上で集合に入っている最小の整数を求める

①と似ているが、クエリ2で同じ $i$ について何回も聞かれる点が異なる。
（①は既に処理が終わった $i$ は更新しないので、その後に書かれている値は正しくないものになっていく）

最初、setに $1～N$ の値を全て入れておく。

クエリ1に対しては、setから $i$ をdeleteする。
クエリ2に対しては、lower_boundが使える。

または、setに入れる値を値が残っている区間 $[L,R)$ にして、取り除く操作を区間の分割で表現することもできる。

取り除くのみで、加えることはしない場合に限られる。

「整数が存在するか」と
「存在しなかった場合に確認する次の整数」を管理する長さNの配列を用意

i   1  2  3  4  5  6  7  8  9
  [ 1  1  1  1  1  1  1  1  1 ]    0:存在しない  1:する
  [ 2  3  4  5  6  7  8  9  x ]    次の整数

クエリ2: i=7 に対する答え
  [ 1  1  1  1  1  1 [1] 1  1 ]    7が存在するのでそのまま7が答え
  [ 2  3  4  5  6  7  8  9  x ]    

クエリ1: i=4,5 を取り除く
  [ 1  1  1 [0  0] 1  1  1  1 ]    ←該当位置を0にする
  [ 2  3  4  5  6  7  8  9  x ]    ←クエリ1では特に何もせずそのまま

クエリ2: i=4 に対する答え
  [ 1  1  1 [0] 0  1  1  1  1 ]    i=4がないので
  [ 2  3  4 [5] 6  7  8  9  x ]    次に確認すべき5を見に行く

  [ 1  1  1  0 [0] 1  1  1  1 ]    i=5もないので
  [ 2  3  4  5 [6] 7  8  9  x ]    次の6を見に行く
  
  [ 1  1  1  0  0 [1] 1  1  1 ]    i=6はあったので、6が答え
  [ 2  3  4  5  6  7  8  9  x ]    

  後処理
  [ 1  1  1  0  0  1  1  1  1 ]    辿ってきたiについて、
  [ 2  3  4 [6  6] 7  8  9  x ]    存在が確認できた整数に更新しておく

クエリ1: i=6 を取り除く
  [ 1  1  1  0  0 [0] 1  1  1 ]    ←該当位置を0にする
  [ 2  3  4  6  6  7  8  9  x ]    

クエリ2: i=4 に対する答え
  [ 1  1  1 [0] 0 [0][1] 1  1 ]    同様に4→6→7と辿って、
  [ 2  3  4 [6] 6 [7] 8  9  x ]    7があったので7が答え
  
  後処理
  [ 1  1  1  0  0  0  1  1  1 ]
  [ 2  3  4 [7] 6 [7] 8  9  x ]    更新

一度辿った値についてはスキップできるので、償却するとクエリ2を1回あたり $O(\log{N})$ で行えるようになる。

無理。BITなどを使いましょう。

• 平衡二分木を実装する - Qiita

上記で紹介されている平衡二分探索木。結構速いみたい。

• 制約
  • 載せられるのは整数値のみ
    • $1～2^K-1$ までの整数値を入れられて、$K$ は最初に決定する必要がある（後から拡張はやろうと思えばできる）
  • 同じ値は複数持てない

• できること（$N=2^K$ として）
  • 挿入 $O(\log{N})$
  • 削除 $O(\log{N})$
  • ある値が存在するかの検索 $O(\log{N})$
  • ある値より大きい・小さい直近の値の検索 $O(\log{N})$

メリットとして、入れる値が整数なら上限値が $10^9$ などのように大きくても座標圧縮が必要ない。
（BIT木のように最初に配列を作るのでは無く、挿入ごとにノードインスタンスを作るので）

アイデアとしては、各ノードは、自身の位置に応じたpivot値を持つ。

たとえば値 $x$ を挿入するとき「上から挿入箇所を辿っていって、pivot値が $x$ と等しいノードに来たら $x$ はそこでFIXし、代わりにそこに入っていた元の値の挿入箇所をその地点から探し始める」ようなことを行う。

これにより、高さが最初に決めた $K$ 以上にならないことが保証されるとともに、他の平衡二分探索木で発生する「回転操作」、つまりは左右の子を繋ぎ替えるなど、値の書き換えを減らしている。

ピボット値を小数範囲に拡張して、$0.5, 0.25, 0.125, ...$ 単位まで探索できるようにする。

ただし、探索深さの上限が保証されなくなる。（まぁ、極端に狭い範囲に多くの値が集中しない限り実用的に問題となることは少ないはず）

bitshiftして1整数にまとめてやる。

値の上限が大きくなると計算量も増えるが、例えば上限 $10^6$ の整数を3つ管理しても約 $2^{60}$、$K=60$ なので、そこまで無理なものではない。

辞書などで各値の個数を管理して、削除時に個数が“0”にならない限りノードは削除しない、みたいな拡張でいけそう。

ノードに自身の部分木以下のノードの個数を持たせておく。

同じ値を持て、$k$ 番目も求められるようにした

• GitHub - tatyam-prime/SortedSet

そもそも単なるリスト（配列）でも、ソートされていれば検索は二分探索を使えば $O(\log{N})$ でいける。
計算量的に問題となるのは、ソート状態を保ちつつの要素の挿入や削除。要素を1つずつずらすのに $O(N)$ かかる。

[ 2  3  5  9 ]     4 を挿入
         ↘ ↘
[ 2  3  4  5  9 ]  入ってる要素数、または後ろにある要素数だけ値のコピーが発生

これを、「$\sqrt{N}$ 個のリストに $\sqrt{N}$ 個の要素が入った状態」として管理することで、 挿入・削除を平均 $O(\sqrt{N})$ にしてしまおうというアイデア。

どのリストに入っているかの検索に新たなコストが発生するものの、そこそこ高速に動作する。

挿入・削除を繰り返すと徐々に要素数にばらつきが出てくるので、定期的に再構築する。

またデータ型が整数値など単純なものであれば、listを使うよりarray.arrayを使った方が高速に動作する？

• array --- 効率のよい数値アレイ — Python ドキュメント

メリットとして、巨大な値、小数値、タプル、その他も大小が定義できれば、そのまま入れられる。