range minimum query(RMQ)とは、整列集合の列上で区間内の最小値を求めるという問題である。最小値の場所を求めるというバリエーションもある。

lowest common ancestorと深い関係があり、両者を還元することができ、解くのにも使われる。 クエリ問題版では、lowest common ancestorに還元する前処理$Θ(n)$, クエリ$Θ(1)$のアルゴリズムが存在する。

定義

整列集合の列$A$と、区間を表す2つの整数$0 \le l \le r \lt |A|$に対して、 $$RMQ_{A}(l, r) = \min_{a \in A[l,r]} a$$ を$A,l,r$の区間最小値といい、それを求める問題をrange minimum queryという。

クエリ問題

列が事前に与えられる。 クエリでは区間が与えられて入力のRMQを求める。

動的問題

列に対して初期状態を求める。 RMQクエリでは内部状態と区間が与えられて入力のRMQを求める。

パラメータ

• $n = |A|$

自明な還元

最大値を求める

要素の順序を反転させれば良い。

最小値の位置を求める

列を$A' = zip(A, [0 \cdots])$とし、順序を辞書式順序にすれば位置も一緒に求めることができる。

アルゴリズム

segment tree

"segment tree"を用いると、要素の変更クエリなどに対応した動的問題版を$Θ(\log n)$で解くことができる。

クエリ問題版にも適用でき、その場合、前計算$Θ(n)$時間, $Θ(n)$空間, クエリ$Θ(\log n)$時間を達成する。

平衡探索木

"平衡探索木"を用いると、区間の移動や反転などさらなる操作に対応でき、クエリ$Θ(\log n)$時間を達成する。

sparse table

sparse table(ST)では、全ての区間$A[l,l + 2^k - 1]$の最小値を事前計算する。 この事前計算は動的計画法により計算できる。 クエリでは、入力区間を被覆しかつはみ出さないように、2つの事前計算した区間を撰ぶ。これには$\log_2 (r-l+1)$の計算が必要になるが、これは事前計算しておけばよい。

クエリ問題版を、前計算$Θ(n \log n)$時間, $Θ(n \log n)$空間, クエリ$Θ(1)$時間で解くことができる。

lowest common ancestorへの還元

"Cartesian tree"という根付き木に入力を変換することでlowest common ancestor問題へと還元できる。詳細は"Cartesian tree"を参照。

クエリ問題版で前計算$Θ(n)$時間, $Θ(n)$空間, クエリ$Θ(1)$時間を達成する。

±RMQ

±RMQ (± range minimum query)とは、整数列のRMQであって、「隣接する要素の差が±1」という条件をつけたものである。

最小値の位置を求めるように拡張できる。この場合、位置は関係なく隣接する実際の要素の差が±1という条件となる。

lowest common ancestorは区間最小値の位置を求めるように拡張された±RMQに還元することができる。

±RMQアルゴリズム

±1であるという条件を用いて"#Sparse Table"に拡張を加えて高速化できる。

入力を$\frac{\log n}{1 + \epsilon}$のサイズのブロックへ分割する。 そのブロックを1要素と考えてsparse tableを適用する。これは$O(\frac{n}{\frac{\log n}{1 + \epsilon}} \log n) = O(\frac{n (1 + \epsilon)}{\log n} \log n) = O(\frac{n}{\log n} \log n) = O(n)$の時間・空間で計算できる。

問題はブロック中の"エッジ"ケースだが、これは以下のトリックによって解決できる。

$\frac{\log n}{1 + \epsilon}$サイズのブロックの中を「$\{＋,－\}$の列」として考えたとき、相違なる個数は、$O(2^{\frac{\log n}{1 + \epsilon}}) = O(n^{\frac{1}{1 + \epsilon}})$個である。 それぞれに対して$O(\log^2 n)$のテーブルを事前計算しても、$O(n^{\frac{1}{1 + \epsilon}} \log^2 n) ⊆ O(n)$の時間・空間しかかからない。 さらにブロックごとに最初の値を記録しておけばブロック中の任意のRMQが求められる。

クエリではまずブロック中のエッジ部分をテーブルによって求め、さらに区間が覆うブロック列でsparse tableのクエリを使って求め、それらの最小値を取る。

クエリ問題版で前計算$O(n)$時間, $O(n)$空間, クエリ$Θ(1)$時間を達成する。