Mae向きなブログ

Mae向きな情報発信を続けていきたいと思います。

Range Minimum Query (RMQ)

Ruby

AOJの「Range Minimum Query(RMQ)問題」に取り組んでみました。

要約すると、数列A = \{a_0, a_1,...,a_{n-1}\}に対し、次の2つの操作を行うプログラムを作成する問題です。

  • update(i,x): a_iをxに変更する。
  • find(s, t): a_s, a_{s+1},...,a_tの最小値を出力する。

単純で非効率なアルゴリズムならすぐに思いつきますが、効率の良いアルゴリズムとなると先人の知恵をお借りした方が良さそうです。参考サイトのスライドを頼りにというか、ほとんどそのままRubyで実装してみました。再帰を用いたqueryメソッドの実装が素晴らしいなと思います。

rmq.rb

参考

参考サイトのスライドの最初の方に、Union-Find木についての説明がありますが、これについて以前取り組んだものが以下です。