-
\(ST\) 表是倍增的产物，一般用来求解区间最值问题
-
那么如何实现 \(ST\) 表，实际上很简单。
-
因为 \(log2(2)=1\) ，所以对于每一个长度为 \(1\) 的区间，数组第二维一定是 \(0\) ，即 \(\LARGE{f{_i}{_,}{_0}=a_i}\)
-
对于每一个更大的区间，一定是通过左右两个小区间求出来的，所以 \(\LARGE{f{_i}{_,}{_j}=max(f{_i}{_,}{_{j-1}},f{_{i+2^{(j-1)}}}{_,}{_{j-1}})}\) 其中 \(\LARGE{2^{j-1}}\) 是小区间的长度， \(\LARGE{2^j}\) 是大区间的长度。
-
对于每个查询，可以求出 \(\LARGE{k=log(r-l+1)}\) ，之后将 \(\LARGE{max(f{_l}{_,}{_k},f{_{r-2^{k}+1}{_,}{_k}})}\) 作为区间最大值输出。
-
我们发现，两个区间是有重叠的，但是想一想，区间极值与区间和是不同的，因为 \(\LARGE{max(k,k)=k}\) ，所以即使区间发生了重叠，对最终结果也没有影响。
-
所以 \(ST\) 表初始化代码如下
inline void RMQ()
{
logg[0]=-1;
for(int i=1;i<=n;++i)f[i][0]=read(),logg[i]=logg[i>>1]+1;
for(int i=1;i<=n;++i)
int t=log(n)/log(2);
for(int j=1;j<=t;++j)for(int i=1;i+(1<<j)<=n+1;++i)
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
- 查询代码如下
inline int ST_query(int l,int r)
{int k=logg[r-l+1];return max(f[l][k],f[r-(1<<k)+1][k]);}
(压行可能比较严重)
- \(ST\) 板子
#10123. 「一本通 4.2 练习 2」Balanced Lineup
- 其中第一题只需要求区间最大值，只需要用一个数组 \(f\) 存下最大值即可，之后 \(O(1)\) 查询
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 100010
using namespace std;
int f[N][18],n,m;
int logg[N];
inline int read()
{
register int x=0;register bool f=1;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar())if(c=='-')f=0;
for(;'0'<=c&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
return f?x:~x+1;
}
void write(int x)
{
if(x<0)putchar('-'),x=~x+1;
if(x>9)write(x/10);
putchar((x%10)+'0');
}
inline void RMQ()
{
//for(int i=1;i<=n;++i)f[i][0]=a[i];
logg[0]=-1;
for(int i=1;i<=n;++i)logg[i]=logg[i>>1]+1;
int t=log(n)/log(2);
for(int j=1;j<=t;++j)for(int i=1;i+(1<<j)<=n+1;++i)
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
inline int ST_query(int l,int r)
{int k=logg[r-l+1];return max(f[l][k],f[r-(1<<k)+1][k]);}
inline int max(int x,int y){return x>y?x:y;}
signed main(void)
{
int x,y,i,j;
n=read(),m=read();
for(i=1;i<=n;++i)f[i][0]=read();
RMQ();
for(i=1;i<=m;++i)x=read(),y=read(),write(ST_query(x,y)),puts(" ");
return 0;
}