ST表 RMQ（区间最大/最小值查询）问题-526互联

主要应用倍增思想
预处理：O(nlogn) 查询：O(1)
f[i][j]是以i为起点，长度为2j的区间中的最大值(一个点一个单位长度，不是一条线段)
区间终点：i+2^j-1<=n
区间长度的指数k=log₂(r-l+1)，只有当r-l+1为2ⁿ-1时是恰好分割，其他时候有重叠，但问题不大

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int f[100005][22];

int main(){
  int n,m; scanf("%d%d",&n,&m);
  
  for(int i=1;i<=n;i++) scanf("%d",&f[i][0]);
  for(int j=1;j<=20;j++) //枚举区间长度，应该是由logn决定
    for(int i=1;i+(1<<j)-1<=n;i++) //枚举起点
      f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
  
  for(int i=1,l,r;i<=m;i++){
    scanf("%d%d",&l,&r);
    int k=log2(r-l+1); //区间长度的指数
    printf("%d\n",max(f[l][k],f[r-(1<<k)+1][k]));
  }
}

凡是符合结合律且可重复贡献的信息查询都可以使用ST表。
例如最大值、最小值、最大公因数、最小公倍数、按位或、按位与都符合
ST表不可进行修改操作，要修改得换线段树