rmq st算法求区间最值问题

st算法是解决区间最值问题比较有效的算法，把每一段查询区间分为两部分，用nlogn的预处理求出dp[i][j]从第i个数开始到i+2^j-1之间的最值，如果要查询[a,b]的最值，则可分为[a,a+2^k-1],[b-2^k+1,b-2^k+1+2^k-1]即[b-2^k+1,b]两个区间每次查询的时间为o(1)其中k=(int)(log(b-a+1)/log2)(换底公式)

View Code

 1 #define N 100005
 2 int dp[N][18];
 3 int v[N];
 4 int max(int a,int b)
 5 {
 6     return a>b?a:b;
 7 }
 8 int rmq(int s,int e)
 9 {
10     int k=(int)(log((e-s+1)*1.0)/log(2.0));
11     return max(dp[s][k],dp[e-(1<<k)+1][k]);
12 }
13 int makrmq(int n)
14 {
15     int i,j;
16     for(i=1;i<=n;i++)
17     dp[i][0]=v[i];
18     for(j=1;(1<<j)<=n;j++)
19     for(i=1;i+(1<<j)-1<=n;i++)//动态规划的思想求最值
20     dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
21 }