ST表

利用ST表可以在及快的时间内查询静态区间的最大值，但只能是求静态的

倍增思想

ST表利用了倍增的思想去求区间最值问题 什么是倍增思想？ 比如 从1开始的两格内的最大值是3，意思是 max[1,2]=3,然后，从3开始，两格内的最大值是5, 意思是max[3,4]=5,那么从1开始的四格内的最大值就是 max( [1,2],[3,4])=5。按照指数增长去更新区间最大值的方法就是倍增，这个思想就是倍增思想。

预处理

1.提前处理出，$x=2^i$ 中 i 是多少==ln x。

for(int i=2;i<=n;i++) mn[i]= i&(i-1) ? mn[i-1]:mn[i-1]+1;

这个代码的意思是 比如一个数 i = 8 = 1000 , i-1=7=0111。 i & i-1 = ( 1000 ) & ( 0111 ) = 0 , 那么当x=8的时候 , 取的是 mn[i-1]+1,就是 比x=7的时候多一位。

2.从x为开始，每多倍增2区间范围后的最大值为多少 ，要得到[1,4]区间的最大值，所以要求得 [1,2] 和 [3,4]区间的最大值，所以首先枚举倍率，再枚举位置。

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

枚举的顺序大致为$i^1,i^2……$，依次取最大 特别 mx[i][0]=a[i]

RMQ查询函数

查询 l，r 区间内最大的值为多少。

1. 首先[ l , r ] 区间大小为多少,len。

2. max[l,r]=max( max[ l ][ ln(len) ] ,max[ r-(1<<ln(len)+1 ] [ ln(len) ] ) 挺抽象的，看图 意思是我们的右端点肯定是在r上的，但是我们需要向左移动一段距离使得能和左端点重合一部分。举例子好理解。 len=8-2=6,ln len =2

   max[2,8] = max[ 2 ] [ 2+$2^2$-1 ] ,max[ 8-$2^2$+1 , 8-$2^2$+1+$2^2$-1 ]

---> max[ 2 ] [ 5 ] ,max[ 5 ] [ 8 ]

int rmq(int l,int r)
{
  int k=r-l+1;
  return max( mx[l][ mn[k] ] ,mx[ r-( 1<<mn[k] )+1 ][ mn[k] ] );
}

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+12;
int n,m,a[N],mx[N][18],mn[N];
int rmq(int l,int r)
{
  int k=r-l+1;
  return max( mx[l][ mn[k] ] ,mx[ r-( 1<<mn[k] )+1 ][ mn[k] ] );
}
int main(){
  scanf("%d %d",&n,&m);
  for(int i=1;i<=n;i++) scanf("%d",&a[i]),mx[i][0]=a[i];
  for(int i=2;i<=n;i++) mn[i]=i&(i-1) ? mn[i-1]:mn[i-1]+1;
  for(int j=1;( 1<<j )-1<=n;j++ )
  {
    for(int i=1;i+(1<<j)-1<=n;i++)
      mx[i][j]=max( mx[i][j-1],mx[i+(1<<j-1)][j-1] );
  }
  int l,r;
  while(m--)
  {
    scanf("%d %d",&l,&r);
    printf("%d\n",rmq(l,r));

  }



}