什么是RMQ問題：
????RMQ (Range Minimum/Maximum Query)：對于長度為n的數(shù)組A，回答若干詢問RMQ(A,i,j)(i,j<=n-1)，返回數(shù)組A中下標(biāo)在i,j范圍內(nèi)的最小（大）值，也就是說，RMQ問題是指求區(qū)間最值的問題。

1.暴力法最簡單的方法，就是遍歷數(shù)組直接搜索，但是這種方式時間復(fù)雜度是O(n)。對于數(shù)組長度較大，性能要求高的場景不適用。一般用這個算法就等著TLE，時間復(fù)雜度最壞O（Q*N），也不一定超時，簽到題可能就直接讓你過了。

2.ST（Sparse Table）算法
ST算法是一種更加高效的算法，基于動態(tài)規(guī)劃的思想，以O(shè)(nlogn)的預(yù)處理代價，換取O(1)的查詢時性能。但是，是離線的，也就是說每次修改都是O(nlogn)復(fù)雜度，那么用在帶修的題目上就顯得捉襟見肘了。

3.樹狀數(shù)組

從下向上更新，sum改為max/min即可，但是局限性比較大吧，很少看見用樹狀數(shù)組求最值的題解。

4.線段樹是基于分治的思想來實現(xiàn)的，建立是o（nlogn）查詢?yōu)镺（logN),那么也就是說這個可以進(jìn)行修改，單點修改維護(hù)也是logN。

分析也就是說，我們可以拋開1/3不談，當(dāng)題目是離線的時侯使用ST算法更快，當(dāng)題目是在線的時候直接使用線段樹維護(hù)即可，好像還有一種萬能的莫隊，不在考慮范圍之內(nèi)。

對于每種算法，詳解馬上發(fā)布。

總結(jié)

以上是生活随笔為你收集整理的关于RMQ问题的四种解法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。