rmq(int i,int j,int a)表示查询a数组i到j区间的内容中的最大/最小值核心部分为二分区间以及st预处理算法

先说st预处理算法吧

int dp[i][j];//表示以i开始 长度为2^j的区间里面元素的最大值

那么 dp[i][0] 就表示a[i]本身了 那么dp[i][j]怎么求呢？ 我们将需要求的区间二分 2^k为区间二分后的长度 k的求法如下

int k=log(double(n+1))/log(2.0);//n为数组的长度

那么 dp[i][j]=max(dp[i][j-1],dp[i+(1<<j)][j-1]); 这就是st的状态转移方程 也是区间的二分思想 既然我们dp[j]需要dp[j-1]的状态那么 我们写两层循环的时候j的值是顺序的 i的值按循序遍历即可

for(int j=1;j<=k;j++)
{
for(int i=1;i+(1<<j)-1<=n;i++) dp[i][j]=max(dp[i][j-1],dp[i+(1<<j)][j-1]);
}

然后是总的rmq

给个题目吧 hdu 3183

int k=log(double(n+1))/log(2.0);//n为数组的长度
int dp[i][j];//表示以i开始 长度为j的区间里面元素的最大值
for(int i=1;i<=n;i++) dp[i][0]=a[i];//dp的初始化问题
for(int j=1;j<=k;j++)
{
for(int i=1;i+(1<<j)-1<=n;i++) dp[i][j]=max(dp[i][j-1],dp[i+(1<<j)][j-1]);
}
int rmq(int i,int j)
{
int k=log(double(i+j))/log(2.0);
return max(dp[i][k],dp[j-(1<<k)+1][k]);
}

对于st预处理的过程 有两种返回情况  第一种是返回值 第二种是返回值的下标

对于 3183 返回下标比较有用

int st[][]; int Min(int x,int y) { return s[x] <= s[y] ? x : y; //这一步是核心 判断的时候 对应返回的是下标 用下标去对应值 } void RMQ_Init(int len) { for(int i =; i < len; i++)
st[i][] = i; for(int j =; (<<j) < len; j++) for(int i =; i+(<<j)- < len;i++)
st[i][j] = Min(st[i][j-],st[i+(<<(j-))][j-]); } int Query(int l,int r) { int k = (int)(log((double)(r-l+))/log(2.0)); return Min(st[l][k],st[r-(<<k)+][k]); }