再谈 ST 表
思想：倍增。
适用范围：对于一个不可修改的序列维护区间最大/最小值询问。
时间：\(O(n\log n)\) 预处理，\(O(1)\) 查询。
下文以最大值为例。
预处理
状态：设 \(f_{i,j}\) 表示区间 \([i,i+2^j-1]\) 的最大值。
那么递推式就有：
\[f_{i,j}=\max\left\{f_{i,j-1},f_{i+2^{j-1},j-1}\right\}
\]
显然边界是 \(f_{i,0}=a_i\)。其中 \(a_i\) 是原序列。
图解：
其中第二个，区间右边界是 \(i+2^{j-1}+2^{j-1}-1=i+2^j-1\)。
查询
假设查询区间为 \([l,r]\)。
找到 \(\max\left\{k\mid 2^k<r-l+1\le 2^{k+1}\right\}\)。
把 \([l,r]\) 分解为 \([l,l+2^k-1]\cup [r-2^k+1,r]\)。
即从 \(l\) 开始的 \(2^k\) 个元素与 \(r\) 结尾的 \(2^k\) 个元素。
因为 \(2^k<r-l+1\le 2^{k+1}\)，所以这俩区间一定可以覆盖整个查询区间。
对于 \(r-2^k+1\) 的解释：
\[r-2^k+1+2^k-1=r
\]
所以式子就是：
\[\max\left\{f_{l,k},f_{r-2^k+1,k}\right\}
\]
注意：ST 表是预处理完查询，所以不支持修改。
示例代码
例题：P3865 【模板】ST 表 & RMQ 问题
#include<bits/stdc++.h>
using namespace std;
typedef long long ljl;
#define FUP(i,x,y) for(auto i=(x);i<=(y);++i)
#define FDW(i,x,y) for(auto i=(x);i>=(y);--i)
inline void Rd(auto &num);
const int N=1e5+5,L=25;
int n,m,a[N];
namespace ST{int f[N][L],Lg2[N];void Build(){Lg2[1]=0;FUP(i,2,n)Lg2[i]=Lg2[i/2]+1;FUP(i,1,n)f[i][0]=a[i];FUP(j,1,20){FUP(i,1,n){if(i+(1<<(j-1))>n)break;f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);}}return;}int query(int l,int r){int lens=r-l+1;int k=Lg2[lens];return max(f[l][k],f[r-(1<<k)+1][k]);}
}
int main(){Rd(n);Rd(m);FUP(i,1,n)Rd(a[i]);ST::Build();int l,r;while(m--){Rd(l);Rd(r);printf("%d\n",ST::query(l,r));}return 0;
}
inline void Rd(auto &num)
{num=0;char ch=getchar();bool f=0;while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}while(ch>='0'&&ch<='9'){num=(num<<1)+(num<<3)+(ch-'0');ch=getchar();}if(f)num=-num;return;
}