众所周知，

线段树能够做到 \(O(\log n)\) 级别 的预处理，\(O(\log n)\) 级别的区间查询，

可是，

还有一种数据结构，

能够做到 \(O(n\log n)\) 级别的预处理，将区间查询时间复杂度降低到 \(O(1)\) 级别！

这就是 \(\operatorname{ST}\) 表。

正题：

ST表基于 倍增思想 与 动态规划，对于所有 可重复贡献问题，这个数据结构都能做到 \(O(1)\) 时间求解。

可重复贡献问题 是指对于运算 \(\operatorname{opt}\)，满足 \(x\operatorname{opt}x=x\)，则对应的 区间询问 就是一个 可重复贡献问题。
例如，最大值有 \(\max(x,x)=x\)，最大公约数有 \(\gcd(x,x)=x\)，所以 \(\operatorname{RMQ}\) 问题 和 区间 \(\gcd\) 问题 就是可重复贡献问题。
如区间和就 不具有此性质，如果求区间和时采用的预处理区间 出现重叠，则会导致重叠部分被 重复计算。
另外，运算 \(\operatorname{opt}\) 还必须满足结合律才能使用 \(\operatorname{ST}\) 表求解。

现在，我们来考虑用 \(\operatorname{ST}\) 表解决 \(\operatorname{RMQ}\) 问题，也就是 求区间最大值:

我们设 \(ST_{i,j}\) 表示数列 \(a\) 的区间 \((i,i+2^j-1)\) 中的最大值：

\(\because 2^0=1\)

\(\therefore ST_{i,0}=\max_i^{i+2^0-1} a_i\)

\(\therefore ST_{i,0}=\max_i^i a_i\)

\(\therefore ST_{i,0}=a_i\)

根据定义，\(ST\) 数组的第二维就相当于“走了 \(2^j-1\) 步”，所以有状态转移方程：

\(ST_{i,j}=\max(ST_{i,j-1},ST_{i+2^{j-1},j-1})\)

以上就是整个 \(\operatorname{ST}\) 表的 预处理部分。

至于查询，我们可以用以下步骤去解决：

对于一个询问 \((l,r)\)，我们可以定义一个变量 \(s\)，\(s=\lfloor\log_2(r-l+1)\rfloor\)，

则 \(\max_{l,r}=\max(ST_{l,l+2^s-1},ST_{r-2^s+1,r})\)。

由于 \(s\) 代表区间长度 \(len\) 以 \(2\) 底的对数，即 \(\log_2(r-l+1)\)，

所以 能保证 式子 \(\max_{l,r}=\max(ST_{l,l+2^s-1},ST_{r-2^s+1,r})\) 中的两个区间 一定相交，

也就能保证覆盖区间 \((l,r)\)。

前文提到，\(\max\) 操作属于 可重复贡献运算，所以两区间的相交并不影响最终结果。

至此，本问题完结。

下面给出 \(\operatorname{ST}\) 表的模板代码。

Code:

#include
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const int logn=17,N=1e5+5;
int n,m,ST[N][logn+1],Log[N+1];
void pre() //预处理对数数组
{
	Log[1]=0;
	Log[2]=1;
	for(int i=3;i>1]+1;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",ST[i]); //输入序列，也就是输入ST[i][0]
	pre();
	for(int j=1;j<=logn;j++)
	{
		for(int i=1;i+(1<