江苏优化网站,中国建设网站,湛江公司网站建设,备案的网站名称可以改吗RMQ问题
RMQ问题指对于数值#xff0c;每次给一个区间[l,r]#xff0c;要求返回区间区间的最大值或最小值
也就是说#xff0c;RMQ就是求区间最值的问题
对于RMQ问题#xff0c;容易想到一种O#xff08;n#xff09;的方法#xff0c;就是用i直接遍历[l,r]区间…RMQ问题
RMQ问题指对于数值每次给一个区间[l,r]要求返回区间区间的最大值或最小值
也就是说RMQ就是求区间最值的问题
对于RMQ问题容易想到一种On的方法就是用i直接遍历[l,r]区间找出不断比较a[i]与max的大小关系然后不断更新max最后得出的就是最大值
但如果要进行多次查询这个算法就会变得特别慢
于是我们利用倍增和动态规划的思想利用‘ST表’这个数据结构来帮助解决。
ST表
ST表是一种“静态求区间最值”的数据结构本质上是一种dp。
假设我们要求区间的最大值最小值类似设状态st[i][j]表示从i开始大小为2^j的长度的区间的最大值即区间[i,i2^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,22*2-1],[7-2*21,7]的最大值也就是st[2][2],st[7-4][2] 从2开始长度为2的最大值和从5开始长度为2的最大值
拓展一下[l,r]区间需要找出一个k使得2^kr-l1,klog2(r-l1),可以分解为max(st[l][k],st[r-2^k1][k]) 一个是从头开始一个是从尾开始 int getMax(int l,int r){ return max(str[l][k],st[r-(1k)1][k]); } 例题
区间最大值
题目描述
给定一个长度为 N 的数组 a其值分别a1,a2,...,aN。
现有 Q 个询问每个询问包含一个区间请回答该区间的最大值为多少。
输入描述
输入第 11 行包含两个正整数 N,Q分别表示数组 a 的长度和询问的个数。
第 22 行包含 N 个非负整数a1,a2,...,aN表示数组 a 元素的值。
第 3∼Q2 行每行表示一个询问每个询问包含两个整数 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
5
package ST;
import java.util.*;
public class chapter1 {public static void main(String[] args) {// TODO Auto-generated method stubScanner scannew Scanner(System.in);int nscan.nextInt();int qscan.nextInt();long []anew long [n];for(int i0;in;i) {a[i]scan.nextLong();}int m(int)Math.ceil(Math.log(n)/Math.log(2));//对m进行向上取整2^nlong [][] stnew long [n][m];for(int i0;in;i) {st[i][0]a[i];}for(int k1;km;k) {for(int i0;i(1k)n;i) {st[i][k]Math.max(st[i][k-1],st[i(1(k-1))][k-1]);}}while(q--0) {int lscan.nextInt()-1;//数组从0开始所以需要减1int rscan.nextInt()-1;int lenr-l1;int k(int)(Math.log(len)/Math.log(2));int max (int) Math.max(st[l][k],st[r-(1k)1][k] );System.out.println(max);}}}
