- できるだけ毎週土曜日更新．次回更新は2月16日．
- ネタ切れ深刻なので記事リクエスト募集中．twitterないしはコメント欄まで．
- 貼っているコードはあんまり検証していないので，信頼性はアレです．アレ．
- twitter: @tmaehara フォローはお気軽に．
2012-09-09
次回予告
次回は次の問題に答えるテクニックを紹介します．興味のある人は考えてみてください．ネタバレ禁止とかは特に無いので，解答を思いついた方は是非トラックバックでも飛ばしてください（＝宣伝活動）．
ちなみに：問題１は多くの人が解けると思います．事前知識なしで問題２を思いついた方は自慢できます．１・２は実装量はたいしたことはありません．
問題１（簡単）
n 個の数が与えられる．クエリとして
- get(i): i 番目の数を返す
- addRange(i, j, x): i～j 番目の数に x を足す
がたくさん飛んでくるので，答えよ．
問題２（普通）
n 個の数が与えられる．クエリとして
- get(i): i 番目の数を返す
- addRange(i, j, x): i～j 番目の数に x を足す
- minRange(i, j): i～j 番目の数の中で最小の値を返す
がたくさん飛んでくるので，答えよ．
問題３（難）
n 個の数が与えられる．クエリとして
- get(i): i 番目の数を返す
- addRange(i, j, x): i～j 番目の数に x を足す
- minRange(i, j): i～j 番目の数の中で最小の値を返す
- insert(i, x): i 番目に新たに数 x を挿入する
- remove(i): i 番目の数を削除する
がたくさん飛んでくるので，答えよ．
想定は普通の平衡二分探索木で，回転時に適切な更新を要するアレでしたが，addを遅延評価するのが主流みたいで，確かにそのほうが実装容易ですね．ぐぬぬ．