您好,登錄后才能下訂單哦!
RMQ是詢問某個區(qū)間內的最大值或最小值的問題,ST算法可以求解RMQ問題.ST算法通常用在要 多次詢問某一些區(qū)間的問題中,相比于線段樹,它的程序實現(xiàn)更加簡單,運行速度更快,它可以做到O(nlogn)的預處理,O(1)回答每個問題.使用ST算法的條件是沒有修改操作,因此它適用于沒有修改操作并且訪問次數(shù)較多(10^6級別甚至更大)的情況.
1.預處理
ST算法的原理實際上是動態(tài)規(guī)劃,首先要知道f數(shù)組的含義,f[i][j]中i表示左邊端點,j表示2^j個長度, 因此f[i,j]表示的是區(qū)間為[i,i+2^j-1]這個范圍內的最大值,也就是以a[i]為起點連續(xù)的2^j個數(shù)的最大值.由于元素個數(shù)為2^j個,所以從中間平均分成兩部分,每一部分的個數(shù)都為2^(j-1);假設f[6][3]分為f[6][2]和f[10][2],如下圖所示,
整個區(qū)間的最大值一定是左右兩部分最大值的較大者,滿足動態(tài)規(guī)劃的最優(yōu)化原理,分析得f數(shù)組的狀態(tài)轉移方程為f[i][j]=max(f[i][j-1],f[i+2^(j-1)][j-1]).
for(int j = 1;(1<<j) <= n;++j) //j枚舉每一個可能出現(xiàn)的長度
for(int i = 1;i + (1<<j)-1 <= n;i++) //i枚舉每一個區(qū)間的左端點
f[i][j] = max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
2.詢問
當要訪問區(qū)間[L,R]的最大值,需要知道區(qū)間的長度len,mn數(shù)組存放的是小于等于一定長度len的最大的2的冪次,若要訪問區(qū)間[5,10]的最大值,則要先計算出men[len]的值,那么區(qū)間[5,10]=[5,8]U[7,10].
代碼實現(xiàn)
//對于一定長度的區(qū)間len,mn[len]表示小于等于len的最大的2的冪次
for(int len = 1;len <= n;++len)
{
int k = 0;
while(1<<(k+1) <= len)
k++;
mn[len] = k;
}
3.求區(qū)間[x,y]最大值
int k = mn[R - L + 1];
ans = max(f[L][k],f[R-(1<<k)+1][k]);
代碼實現(xiàn)
#include<iostream>
using namespace std;
const int maxn=1e6+5;
int f[maxn][25];
int mn[maxn];
int a[maxn];
int m,n;
void rmq_init()
{
//初始化所有長度為1的區(qū)間的最大值
for(int i = 1;i <= n;i++)
f[i][0] = a[i];
for(int j = 1;(1<<j) <= n;++j) //j枚舉每一個可能出現(xiàn)的長度
for(int i = 1;i + (1<<j)-1 <= n;i++) //i枚舉每一個區(qū)間的左端點
f[i][j] = max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
//對于一定長度的區(qū)間len,mn[len]表示小于等于len的最大的2的冪次
for(int len = 1;len <= n;++len)
{
int k = 0;
while(1<<(k+1) <= len)
k++;
mn[len] = k;
}
}
int rmq(int L,int R)
{
int s = mn[R-L+1];
int ans = max(f[L][s],f[R - (1<<s) + 1][s]);
return ans;
}
int main()
{
cin>>n;
for(int i = 1;i <= n;i++)
cin>>a[i];
rmq_init();
int L,R;
cin>>m;
for(int i = 1;i <= m;i++)
{
cin>>L>>R;
cout<<rmq(L,R)<<endl;
}
return 0;
}
結果截圖
免責聲明:本站發(fā)布的內容(圖片、視頻和文字)以原創(chuàng)、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關證據(jù),一經查實,將立刻刪除涉嫌侵權內容。