差分
このページの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++%%コードを埋め込んで外部モジュールとしてコンパイル | * %%C++%%コードを埋め込んで外部モジュールとしてコンパイル | ||
| - | * 下記、参考の3つめのリンク参照 | + | * [[https:// |
| + | * Pythonでも高速に動く平衡二分木を使う | ||
| + | * [[https:// | ||
| * 参考 | * 参考 | ||
| * [[https:// | * [[https:// | ||
| * [[https:// | * [[https:// | ||
| - | * [[https:// | ||
| 行 50: | 行 51: | ||
| * 値 $x$ を追加 → $bit.add(x, 1)$ | * 値 $x$ を追加 → $bit.add(x, 1)$ | ||
| * 値 $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})$| | |erase |$O(\log{N})$| | ||
| |upper_bound \\ lower_bound|$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$ から本来の値を入れる、などで本当の値と区別できる。 | ||
| + | |||
| + | === 例 === | ||
| + | |||
| + | 累積和 | ||
| + | 初期状態 | ||
| + | [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, | ||
| + | [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} | ||
| + | | ||
| + | | ||
| + | | ||
| + | 6以上の最小の値を取得 | ||
| + | [0 1 3 3 4 4 5 5] {2, 3, 3, 5, 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} | ||
| + | | ||
| + | |||
| === バリエーション === | === バリエーション === | ||
| 行 147: | 行 192: | ||
| ++++ | ++++ | ||
| - | === std::set解 === | + | === std::set解（想定解） |
| std:: | std:: | ||
| 行 232: | 行 277: | ||
| 自身の値 " | 自身の値 " | ||
| + | |||
| + | ==== ピボット木 ==== | ||
| + | |||
| + | * [[https:// | ||
| + | |||
| + | 上記で紹介されている平衡二分探索木。結構速いみたい。 | ||
| + | |||
| + | * 制約 | ||
| + | * 載せられるのは整数値のみ | ||
| + | * $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$ 以上にならないことが保証されるとともに、他の平衡二分探索木で発生する「回転操作」、つまりは左右の子を繋ぎ替えるなど、値の書き換えを減らしている。 | ||
| + | |||
| + | === バリエーション === | ||
| + | |||
| + | == 同じ値を持つ == | ||
| + | |||
| + | 辞書などで各値の個数を管理して、削除時に個数が" | ||
| + | |||
| + | == $k$ 番目を求める == | ||
| + | |||
| + | ノードに自身の部分木以下のノードの個数を持たせておく。 | ||
