差分

このページの2つのバージョン間の差分を表示します。

--- programming_algorithm:data_structure:balancing_binary_search_tree:tree_free [2020/06/29] – [代替方法一覧] ikatakos
+++ programming_algorithm:data_structure:balancing_binary_search_tree:tree_free [2021/09/06] – ikatakos
@@ 行 28: / 行 28: @@
     * 列挙していけば何か共通点みたいなのが見つかるかも知れない
   * %%C++%%コードを埋め込んで外部モジュールとしてコンパイル
-    * 下記、参考の3つめのリンク参照
+    * [[https://nagiss.hateblo.jp/entry/2020/06/28/012528|[Python]平衡二分木が必要な時に代わりに何とかする変なテク[競プロ] - 菜]]
+  * Pythonでも高速に動く平衡二分木を使う
+    * [[https://qiita.com/Kiri8128/items/6256f8559f0026485d90|平衡二分木を実装する - Qiita]]
   * 参考
     * [[https://qiita.com/drken/items/1b7e6e459c24a83bb7fd#2-%E3%81%A4%E3%81%AE-priority_queue|k 番目の値を高速に取り出せるデータ構造のまとめ - BIT上二分探索や平衡二分探索木など - Qiita]]
     * [[https://qiita.com/Salmonize/items/638da118cd621d2628d1|【Python】平衡二分木が必要な時に代わりに何とかするテク【競プロ】 - Qiita]]
-    * [[https://nagiss.hateblo.jp/entry/2020/06/28/012528|[Python]平衡二分木が必要な時に代わりに何とかする変なテク[競プロ] - 菜]]
@@ 行 50: / 行 51: @@
   * 値  $x$  を追加 →  $bit.add(x, 1)$
   * 値  $x$  を削除 →  $bit.add(x, -1)$
-  *  $k$  番目の値を取得 → 累積和が  $k$  以上になる最小のindexを取得
+  *  $k$  番目の値を取得 →  $bit.lower\_bound(k)$ （累積和が  $k$  以上になる最小のindexを取得）
+  *  $x$  以下の最大の値を取得  $bit.lower\_bound(bit.sum(x))$
+  *  $x$  以上の最小の値を取得  $bit.lower\_bound(bit.sum(x - 1) + 1)$
 ^機能  ^計算量      ^
@@ 行 56: / 行 59: @@
 |erase | $O(\log{N})$ |
 |upper_bound \\ lower_bound| $O(\log{N})$ |
+ $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]    {}
+を追加
+            [0 0 0 0 1 1 1 1]    {5}
+を追加
+            [0 0 1 1 2 2 2 2]    {3, 5}
+  小さい方から2番目を取得
+            [0 0 1 1 2 2 2 2]    {3, 5}
+                     ^                            累積和で"2"が始まるiは「5」
+,3,7を追加
+            [0 1 3 3 4 4 5 5]    {2, 3, 3, 5, 7}
+以下の最大の値を取得
+            [0 1 3 3 4 4 5 5]    {2, 3, 3, 5, 7}
+                   ~                              累積和で 4 の箇所は"3"
+                 ^                                累積和で "3" が始まるiは「3」
+以上の最小の値を取得
+            [0 1 3 3 4 4 5 5]    {2, 3, 3, 5, 7}
+                     ~                            累積和で 6-1=5 の箇所は"4"
+                         ^                        累積和で 4+1=5 が始まるiは「7」
+を削除
+            [0 1 3 3 4 4 4 4]    {2, 3, 3, 5}
+以上の最小の値を取得
+            [0 1 3 3 4 4 4 4]    {2, 3, 3, 5}
+                             ^                    存在しない場合、N+1 が返る点には注意
 === バリエーション ===
@@ 行 147: / 行 192: @@
 ++++
-=== std::set解 ===
+=== std::set解（想定解） ===
 std::setであれば、値の小さい順に「要素のindex」をinsertしていく方法が考えられる。
@@ 行 232: / 行 277: @@
 自身の値 "未満" なら……どうやればいいだろうね。
+==== ピボット木 ====
+  * [[https://qiita.com/Kiri8128/items/6256f8559f0026485d90|平衡二分木を実装する - 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値を持つ。
+たとえば値  $k$  を挿入するとき「上から挿入箇所を辿っていって、pivot値が  $k$  と等しいノードに来たら  $k$  はそこでFIXし、代わりにそこに入っていた元の値の挿入箇所をその地点から探し始める」ようなことを行う。
+これにより、高さが最初に決めた  $K$  以上にならないことが保証されるとともに、他の平衡二分探索木で発生する「回転操作」、つまりは左右の子を繋ぎ替えるなど、値の書き換えを減らしている。
+=== バリエーション ===
+== 同じ値を持つ ==
+辞書などで各値の個数を管理して、削除時に個数が"0"にならない限りは削除しない、みたいな拡張でいけそう。
+==  $k$  番目を求める ==
+ノードに自身の部分木以下のノードの個数を持たせておく。