はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける平衡二分木問題まとめ

平衡二分木

  • 平衡二分木はただ順番が正しく守られている二分木
  • 順番ってなんだって感じですが、「数列としての順番」「値の大小としての順番」のどちらでもよくて、このへんはinsertするときに自分でちゃんと合うようにやる
  • 実装が色々あるが、求められるクエリは同じ

1. split, merge(どんな処理でも共通)
2. insert, erase(どんな順番で考えるかによってココを変える)
3. その他の処理

  • 永続平衡二分木という闇もある 永続化できる実装は限られているようです (この問題では+遅延評価まで求められる)
  • 平衡二分木は「数列タイプ」と「setタイプ」があるので、最初はちょっと違う別物として分けたほうが分かりやすいと思う(二分木なのでデータがソートされて入ってそうだが、数列タイプの方はソートされた状態では入ってないので(数列のindex的にはソートされてるんだけど) )
  • 遅延評価を組み込む時はpushタイプがオススメ

http://hamayanhamayan.hatenablog.jp/entry/2017/04/06/105732hamayanhamayan.hatenablog.jp

問題

数列・セグメントツリータイプ

setタイプ

どっちだろう