ST表

RMQ，ST表

題目連結

ST表

給定一個長度為 \(N\) 的數列，和 \(M\) 次詢問，求出每一次詢問的區間内數字的最大值。

第一行包含兩個整數 \(N,M\)，分别表示數列的長度和詢問的個數。

第二行包含 \(N\) 個整數（記為 \(a_i\)），依次表示數列的第 \(i\) 項。

接下來 \(M\) 行，每行包含兩個整數 \(l_i,r_i\) ，表示查詢的區間為 \([l_i,r_i]\)。

輸出包含 \(M\) 行，每行一個整數，依次表示每一次詢問的結果。

對于 \(30\%\) 的資料，滿足 \(1\le N,M\le 10\)。

對于 \(70\%\) 的資料，滿足 \(1\le N,M\le {10}^5\)。

對于 \(100\%\) 的資料，滿足 \(1\le N\le {10}^5，1\le M\le 2\times{10}^6，a_i\in[0,{10}^9]，1\le l_i\le r_i\le N\)。

預處理：

時間複雜度：\(O(nlogn)\)

查詢：

時間複雜度：\(O(1)\)