ST表（数据结构中的问题）

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
5

package 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);}}}