セグメント木で Range Minimum Query (RMQ)

AOJ セグメント木

Quiz

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A

Submission

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3565113#1

解法

範囲内の最小値を求めるセグメント木を作ればよい

その他

  • Range Sumのセグ木を持っていたのでそれを書き換えて書いたが手間取った
  • 主な変更箇所
    • 範囲外である時、Range Sumなら0を返すが、Range Minの場合はinfを返す
    • 値が更新された時の親への反映の仕方

Range Sum Queryの問題もあるよ