簡介
範圍最值查詢
範圍最值查詢
範圍最值查詢若，條件為的範圍最值查詢返回1，它是子數組中最小的元素。
通常情況下，數組A是靜態的，即元素不會變化，例如插入、刪除和修改等，而所有的查詢是以離線的方式給出的，即預先並不知道所有查詢的參數。在上述條件下，將數組以特定方式進行預處理即可以使範圍最值查詢在常數時間內得到處理。
範圍最值查詢 範圍最值查詢現有算法可以通過以線性時間對數組進行預處理以獲得之後常數時間的範圍最值查詢處理，其空間複雜度為。範圍最值查詢問題（RMQ）與最低公共祖先（LCA）問題有直接聯繫，它們可以互相轉化。RMQ的算法常常套用在嚴格或者近似子串匹配等問題的處理中。
RMQ問題的常見解決方法有線段樹、ST(倍增)、排序和樸素。
範圍最值查詢
範圍最值查詢樸素算法就是每次查詢都For一遍，時間複雜度。排序法就是新開一個數組記錄數的位置，排序後每次查詢從頭到尾For一遍，找到第一個在區間中的數退出即可。編程複雜度低，但是實際效果可能並不好。最壞情況時間複雜度，但平均情況會比樸素快那么一點。倍增法請參見下面部分。線段樹是最快的算法，但是編程複雜度非常高，因此除非數據很大極少使用。
ST算法
範圍最值查詢建立一個二維數組的整數值。
範圍最值查詢
範圍最值查詢
範圍最值查詢
範圍最值查詢在這個數組中表示範圍中的最大值（例如中的最大值被計為）。
範圍最值查詢建立數組的過程可以在 時間內完成。具體算法類似於動態規劃。以下是C++語言描述的代碼，數組約定從0開始：
範圍最值查詢當我們需要計算一個區間中的最大值（例如時），我們先求出這個區間的長度（即 8-3+1=6）。
範圍最值查詢
範圍最值查詢然後我們算出不大於它的最大 值的指數（即2）。我們要查詢分別以3開頭，和以8結尾的兩個長度為 的區間的最大值。
範圍最值查詢
範圍最值查詢
範圍最值查詢
範圍最值查詢 範圍最值查詢顯然和也就是（ 和）的最大值就是的最大值。查詢的時間是常數，代碼如下：
範圍最值查詢整個程式的時間複雜度是，Q為查詢數。
