平衡二分木
- 平衡二分木はただ順番が正しく守られている二分木
- 順番ってなんだって感じですが、「数列としての順番」「値の大小としての順番」のどちらでもよくて、このへんはinsertするときに自分でちゃんと合うようにやる
- 実装が色々あるが、求められるクエリは同じ
1. split, merge(どんな処理でも共通)
2. insert, erase(どんな順番で考えるかによってココを変える)
3. その他の処理
- 永続平衡二分木という闇もある 永続化できる実装は限られているようです (この問題では+遅延評価まで求められる)
- 平衡二分木は「数列タイプ」と「setタイプ」があるので、最初はちょっと違う別物として分けたほうが分かりやすいと思う(二分木なのでデータがソートされて入ってそうだが、数列タイプの方はソートされた状態では入ってないので(数列のindex的にはソートされてるんだけど) )
- 遅延評価を組み込む時はpushタイプがオススメ
http://hamayanhamayan.hatenablog.jp/entry/2017/04/06/105732hamayanhamayan.hatenablog.jp
問題
数列・セグメントツリータイプ
- AOJ Range Minimum Query (RMQ) (セグメントツリーでできるようなことは平衡二分木で大体できる)
- AOJ RMQ (シフト操作ができる)
- Lucy and Palindromes (反転操作もできる)
- CF443 Tournament (二分探索できるようにソートを保ちつつ保持)
- AC Hash Swapping
setタイプ
- ARC033 C. データ構造
- yukicoder No.649 ここでちょっとQK! 解説
- ARC028 B. 特別賞
- yukicoder No.449 ゆきこーだーの雨と雪 (4)
- AOJ プログラミングコンテスト II
どっちだろう