桓台做网站江西seo推广软件
RMQ问题
RMQ问题指对于数值，每次给一个区间[l,r]，要求返回区间区间的最大值或最小值
也就是说，RMQ就是求区间最值的问题
对于RMQ问题，容易想到一种O（n）的方法，就是用i直接遍历[l,r]区间，找出不断比较a[i]与max的大小关系，然后不断更新max，最后得出的就是最大值
但如果要进行多次查询，这个算法就会变得特别慢
于是，我们利用倍增和动态规划的思想，利用‘ST表’这个数据结构来帮助解决。
ST表
ST表是一种“静态求区间最值”的数据结构，本质上是一种dp。
假设我们要求区间的最大值（最小值类似），设状态st[i][j]表示从i开始，大小为2^j的长度的区间的最大值，即区间[i,i+2^j-1]的最大值
状态转移方程st[i][j]=max[st[i][j-1],st[i+(1<<(j-1))] [j-1]]; (1<<(j-1))相当于2^j-1
分成左右两个相等的区间
注意状态转移的方向和保证区间合法
区间查询
为了查询区间[l,r]的最大值，它可以分解为两个小区间的最大值，例如要求[2,7]的最大值，可以分解为[2,2+2*2-1],[7-2*2+1,7]的最大值，也就是（st[2][2],st[7-4][2]）
从2开始长度为2的最大值，和从5开始，长度为2的最大值
拓展一下，[l,r]区间，需要找出一个k，使得2^k<=r-l+1,k<=log2(r-l+1),可以分解为max(st[l][k],st[r-2^k+1][k]) 一个是从头开始，一个是从尾开始
int getMax(int l,int r){
return max(str[l][k],st[r-(1<<k)+1][k]);
}
例题
区间最大值
题目描述
给定一个长度为 N 的数组 a，其值分别a1,a2,...,aN。
现有 Q 个询问，每个询问包含一个区间，请回答该区间的最大值为多少。
输入描述
输入第 11 行包含两个正整数 N,Q，分别表示数组 a 的长度和询问的个数。
第 22 行包含 N 个非负整数a1,a2,...,aN，表示数组 a 元素的值。
第 3∼Q+2 行每行表示一个询问，每个询问包含两个整数 L,R，表示区间的左右端点.
输出描述
输出共 Q 行，每行包含一个整数，表示相应询问的答案。
输入输出样例
示例 1
输入
5 5
1 2 3 4 5
1 1
1 2
1 3
3 4
2 5
输出
1
2
3
4
5package ST;
import java.util.*;
public class chapter1 {public static void main(String[] args) {// TODO Auto-generated method stubScanner scan=new Scanner(System.in);int n=scan.nextInt();int q=scan.nextInt();long []a=new long [n];for(int i=0;i<n;i++) {a[i]=scan.nextLong();}int m=(int)Math.ceil(Math.log(n)/Math.log(2));//对m进行向上取整，2^nlong [][] st=new long [n][m];for(int i=0;i<n;i++) {st[i][0]=a[i];}for(int k=1;k<m;k++) {for(int i=0;i+(1<<k)<n;i++) {st[i][k]=Math.max(st[i][k-1],st[i+(1<<(k-1))][k-1]);}}while(q-->0) {int l=scan.nextInt()-1;//数组从0开始所以需要减1int r=scan.nextInt()-1;int len=r-l+1;int k=(int)(Math.log(len)/Math.log(2));int max= (int) Math.max(st[l][k],st[r-(1<<k)+1][k] );System.out.println(max);}}}