这里汇集了所有我知道的静态区间最大值做法。
\(O(n)\) 预处理，\(O(n)\) 回答。
每一次询问暴力处理即可。
\(O(n^2)\) 预处理，\(O(1)\) 回答。
预处理出所有的答案。
\(O(n)\) 预处理，\(O(\log n)\) 回答。
维护一棵线段树。
\(O(n\log n)\) 预处理，\(O(1)\) 回答。
维护ST表。
\(O(n)\) 预处理，\(O(\sqrt{n})\) 回答。
对序列分块，预处理出整块的最大值直接查，散块的暴力查。
\(O(n)\) 预处理，期望 \(O(1)\) 回答。
仍然对于原序列分块，预处理出第 \(l\) 个整块到第 \(r\) 个整块的最大值，同时维护出每一个点在它所在块中的前缀最大值和后缀最大值。
这样，对于跨越了块的询问，整块散都可以 \(O(1)\) 查。
但是对于在一个块内的询问，我们仍然只能暴力查，复杂度是 \(O(\sqrt{n})\) 的。
但是，在数据随机的情况下，出现区间左右端点在同一块内的概率是 \(O(\dfrac{1}{\sqrt{n}})\)，所以在数据随机的情况下，期望时间复杂度是 \(O(\sqrt{n}\times\dfrac{1}{\sqrt{n}})=O(1)\) 的。
\(O(n)\) 预处理，\(O(1)\) 回答。
对于上述方法，我们发现最大的问题是块内的。
我们假设块长为 \(B\)，则我们可以预处理所有整块的ST表，时间复杂度是 \(O(\dfrac{n}{B}\log n)\) 的。
考虑如何做到块内 \(O(1)\) 回答。
我们考虑将某个块内的所有点从左到右加入一个单调队列的过程，例如对于序列 \([1,5,3,2,4]\)，有：
| 编号 | 单调栈状态 |
|---|---|
| \(1\) | \(1\) |
| \(2\) | \(5\) |
| \(3\) | \(5,3\) |
| \(4\) | \(5,3,2\) |
| \(5\) | \(5,4\) |
不难发现，对于所有的右端点为 \(r\) 的询问，最终对于答案做贡献的数必然在 \(r\) 对应的单调栈中。具体的，是单调栈中编号 \(\geqslant l\) 的最小编号对应的数。
发现使用状压数组 \(S_i\) 存储对应每一个右端点时，每个点是否在单调栈内，那么每一次的查询是要找到 s[i]>>l 的最低的为 \(1\) 位，这个可以使用 __builtin_ctz O(1)求值。
这样我们对于散块的部分可以做到 \(O(n)\) 预处理，\(O(1)\) 回答。一般块长取 \(B=32\) 以方便使用位运算优化。
例题
Code:
int a[MAXN],Bnum;
int Lm[MAXN],Rm[MAXN];
int stb[MAXN/32+10][30],Log[MAXN/32+10];
int stk[B+1],top;
struct INK{
long long s[B+1];
int *p;
void init(int *num,int lim)
{
p=num;
top=0;
for(int i=1;i<=lim;i++)
{
s[i]=s[i-1];
while(top&&p[stk[top]]<p[i])
s[i]^=(1ll<<stk[top--]);
s[i]^=(1ll<<(stk[++top]=i));
}
}
int get_min(int l,int r){return p[l+__builtin_ctzll(s[r]>>l)];}
}T[MAXN/B+10];
void init(int n)
{
for(int l=1,r;l<=n;l=r+1)
{
Bnum++;
r=min(n,l+B-1);
T[Bnum].init(a+l-1,r-l+1);
Lm[l]=a[l];
for(int i=l+1;i<=r;i++)
Lm[i]=max(Lm[i-1],a[i]);
Rm[r]=a[r];
for(int i=r-1;i>=l;i--)
Rm[i]=max(Rm[i+1],a[i]);
stb[Bnum][0]=Lm[r];
}
for(int i=2;i<=Bnum;i++)
Log[i]=Log[i>>1]+1;
for(int i=1;i<=Log[Bnum];i++)
for(int j=1;j+(1<<i)-1<=Bnum;j++)
stb[j][i]=max(stb[j][i-1],stb[j+(1<<i-1)][i-1]);
}
int STB(int L,int R)
{
int t=Log[R-L+1];
return max(stb[L][t],stb[R-(1<<t)+1][t]);
}
int ques(int l,int r)
{
if(r<l) return 0;
if((l-1)>>5==(r-1)>>5) return T[((l-1)>>5)+1].get_min(((l-1)&(B-1))+1,((r-1)&(B-1))+1);
if(((l-1)>>5)+1==(r-1)>>5) return max(Rm[l],Lm[r]);
else return max(max(Rm[l],Lm[r]),STB(((l-1)>>5)+2,(r-1)>>5));
}