範圍最值查詢

範圍最值查詢（英語：Range Minimum Query），是針對數據集的一種條件查詢。若給定一個數組${\displaystyle A[1,n]}$，範圍最值查詢指定一個範圍條件${\displaystyle i}$到${\displaystyle j}$，要求取出${\displaystyle A[i,j]}$中最大／小的元素。

「RMQ」重新導向至此。關於台中清泉崗機場的IATA代碼，請見「台中清泉崗機場」。

若${\displaystyle A=[3,5,2,5,4,3,1,6,3]}$，條件為${\displaystyle [3,8]}$的範圍最值查詢返回1，它是子數組${\displaystyle A[3,8]=[2,5,4,3,1,6]}$中最小的元素。

通常情況下，數組A是靜態的，即元素不會變化，例如插入、刪除和修改等，而所有的查詢是以在線的方式給出的，即預先並不知道所有查詢的參數。

RMQ問題有預處理${\displaystyle O(n)}$之後每次查詢${\displaystyle O(1)}$的算法^[1]。

範圍最值查詢問題（RMQ）與最近公共祖先（LCA）問題有直接聯繫，它們可以互相轉化。RMQ的算法常常應用在嚴格或者近似子串匹配等問題的處理中。

算法

Sparse Table

建立一個二維數組 ${\displaystyle F[1\dots N][0\dots O(\log _{2}N)]}$ 的整數值。

在這個數組中 ${\displaystyle F[i][j]}$ 表示範圍 ${\displaystyle [i,i+2^{j}-1]}$ 中的最大值（例如 ${\displaystyle [2,5]}$ 中的最大值被計為 ${\displaystyle F[2][2]}$）。

建立數組的過程可以在 ${\displaystyle O(N\log N)}$ 時間內完成。具體算法類似於動態規劃。以下是 C++ 語言描述的代碼，數組約定從 0 開始：

void Initialise(vector<int> &Array)
{
	int Length = (int)Array.size();

	// 长度为 0 时，表示数据自身。
	for (int i = 0; i < Length; ++i) F[i][0] = Array[i];

	for (int j = 1; (1 << j) <= Length; ++j)
		for (int i = 0; i + (1 << j) - 1 < Length; ++i)
			F[i][j] = min(
				F[i][j - 1], F[i + (1 << (j - 1))][j - 1]
			); // 分成长度相等的两段
}

當我們需要計算一個區間中的最大值（例如 ${\displaystyle [3,8]}$ 時），我們先求出這個區間的長度（即 8 - 3 + 1 = 6）。

然後我們算出不大於它的最大 ${\displaystyle 2^{k}}$ 值的指數（即 2）。我們要查詢分別以 3 開頭，和以 8 結尾的兩個長度為 ${\displaystyle 2^{2}}$ 的區間的最大值。

顯然 ${\displaystyle F[3][2]}$ 和 ${\displaystyle F[5][2]}$ 也就是（${\displaystyle [3,6]}$ 和 ${\displaystyle [5,8]}$）的最大值就是 ${\displaystyle [3,8]}$ 的最大值。查詢的時間是常數，代碼如下：

int Query(int Left, int Right)
{
	int i = 0;

	while (1 << (i + 1) <= Right - Left + 1) ++i;

	return min(
		F[Left][i], F[Right - (1 << i) + 1][i]
	);
}

程序預處理的時間複雜度是 ${\displaystyle O(N\log N)}$的，單次詢問的時間複雜度是${\displaystyle O(1)}$的。整個程序的空間複雜度是${\displaystyle O(N\log N)}$。

Method of Four Russians

Method of Four Russians（英語：Method of Four Russians）先對數組進行分塊，再預處理出每個塊里的ST表，以及每個塊的最值構成的數組的ST表。然後每次查詢時，只需算出中間連續幾個塊的最小值與兩邊不完整的塊的最小值的最小值。程序預處理的時間複雜度是 ${\displaystyle O(N\log \log N)}$的，單次詢問的時間複雜度是${\displaystyle O(1)}$的。整個程序的空間複雜度是${\displaystyle O(N\log \log N)}$。還可以再優化，使預處理的時間複雜度是 ${\displaystyle O(N)}$的，單次詢問的時間複雜度是${\displaystyle O(1)}$的，空間複雜度是${\displaystyle O(N)}$。^[2]

數據結構

如果使用線段樹等數據結構，則可以做到預處理的時間複雜度是 ${\displaystyle O(N\log N)}$，單次詢問的時間複雜度是${\displaystyle O(\log N)}$。整個程序的空間複雜度是${\displaystyle O(N)}$。優點是可以支持動態修改。

應用

在Fischer和Heun（2007）中可以找到一些應用。^[3]:3

計算樹中的最近公共祖先

範圍最值查詢可被用於解決最近公共祖先問題^[4][5]。有根樹S中的節點v與w的最近公共祖先是在從根到w和v的路徑上最深的公共節點u（其可能是v或w）。 Gabow, Bentley和Tarjan（1984）表明，最近公共祖先問題可以在線性時間內規約到範圍最值查詢問題。由此可見，與範圍最值查詢問題一樣，最近公共祖先問題可以在常數時間內進行單次查詢，並僅使用線性空間^[3]。