- できるだけ毎週土曜日更新．次回更新は2月16日．
- ネタ切れ深刻なので記事リクエスト募集中．twitterないしはコメント欄まで．
- 貼っているコードはあんまり検証していないので，信頼性はアレです．アレ．
- twitter: @tmaehara フォローはお気軽に．
2012-09-10
コメントを書く
iwiwi2012/09/11 00:00区分木では，値の差分表現の方が僕は好きでそっちをよく使います．平衡二分探索木だと，仰る通り回転で訳が分からなくなるので遅延評価を使います．余談ですが，そういったクエリを抜きにしても回転は頭がこんがらがるので，回転抜きで平衡二分探索木が作れると友人から聞いて以降それをよく使っています．（ここで触れています http://www.slideshare.net/iwiwi/2-12188757）スケープゴート木も回転が要りませんが，あれは split/merge が出来ないのでコンテストでは使用場所が制限されてしまいます．
spaghetti_source2012/09/11 10:22merge-splitベースのtreapですね．あれは素晴らしい．自分は上からのアクセスで済む場合はmerge-split，下からアクセスする必要があれば回転ベースでやっています．scapegoatはそれらと比べてたいして実装が軽くないし，そもそも平衡できる程度の木に使うのは負けた気がして嫌です．笑