關(guān)于ST算法，實際上它本身并不難，它的思想是動態(tài)規(guī)劃。主要用來求RMQ問題，時間復(fù)雜度為O(NlgN+M)?

關(guān)于RMQ問題描述：

輸入N個數(shù)和M次詢問，每次詢問一個區(qū)間[L,R],求第L個數(shù)到R個數(shù)之間的最大值，或者是求最小值。

?

它的原理闡述如下：

對于一個數(shù)組A[0...N-1]，我們用f[i][j]表示A[i]到A[i+2^j-1]，這個范圍內(nèi)的最大值。

由于此區(qū)間的元素個數(shù)很明顯為2^j個，所以我們又可以從中間平分為兩部分，這樣每部分又有2^(j-1)個元素，這樣我們就知道區(qū)間[i,i+2^j-1]可以分為[i,i+2^(j-1)-1]和[i+2^(j-1),i+2^j-1]兩部分，我們只需要求出后面兩個區(qū)間最大值的較大值，就可以知道前面區(qū)間的最大值了。

所以到了這里，很明顯可以寫出狀態(tài)轉(zhuǎn)移方程：

f[i][j]=max(f[i][j-1]，f[i+2^(j-1)][j-1])

當(dāng)然很明顯知道初始化f[i][0]=A[i]

當(dāng)然上面i，j的范圍是多少呢？

現(xiàn)在我們來分析一下：我們已經(jīng)說了如果用上述原理一個區(qū)間的元素是2^j個，而可以知道2^j<=N的，所以這樣就得到j<=log(N)/log(2);??當(dāng)然j還大于等于1

對于i，就直接有i+2^j-1<N就行了。

到了這里，我們就可以把f[i][j]求出來了。

接下來就是query()了。

這個怎么辦呢，其實很容易，我們先求出滿足條件2^x=R-L+1的最大x

這樣我們我們就可以把區(qū)間[L,R]求最值問題轉(zhuǎn)化為了求區(qū)間[L,L+2^x-1]和區(qū)間[R-2^x+1,R]最大值的較大值了，為什么可以這樣做，因為這兩個區(qū)間中間有重疊。

但是這兩個區(qū)間的并一定等于區(qū)間[L,R]，所以到了這里ST算法的原理基本常闡述完畢了。

剩下的就是代碼實現(xiàn)了。

#include <stdio.h> #include <math.h> #define N 1005int m,n; int a[N]; int f[N][N];int max(int a,int b) {return a>b? a:b; }void ST() {int i,j;for(i=0;i<n;i++)f[i][0]=a[i];for(j=1;j<=(int)((log((double)n)/log(2.0)));j++){for(i=0;i+(1<<j)-1<n;i++)f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);} }int query(int L,int R) {int x=(int)(log((double)(R-L+1))/log(2.0));return max(f[L][x],f[R-(1<<x)+1][x]); }int main() {int i,L,R;while(~scanf("%d%d",&n,&m)){for(i=0;i<n;i++)scanf("%d",&a[i]);ST();while(m--){scanf("%d%d",&L,&R);printf("%d\n",query(L-1,R-1));}}return 0; }

?

總結(jié)

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

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