当前位置：首页 > news >正文

【高级数据结构】ST 表

news 2025/10/7 13:45:32

前言

大部分 ST 表能解决的问题树状数组和线段树都能解决，只不过 ST 表的代码实现更加简单。

ST 表可以求解区间 $[l,r]$ 的最值问题等区间查询。

ST表

ST 表的定义

ST 表是利用倍增思想来解决区间问题的，这样可以缩短时间。

例如，我要求 $\large\max\limits_{i=l}^r a_i$ 的值，那么一般的做法就是从 $l$ 枚举到 $r$，然后用 $ans$ 来记录最大值，但是数据大了显然会超时。

所以我们引出了一种新的数据结构 ST 表。

我们定义 $st_{i,j}$ 表示在序列的第 $i$ 项往后 $2^j$ 所包含的序列间的最大值。

ST 表的处理

对于 $i=1$ 的情况来说，我们可以画个图：

那么我们可以发现 $st_{1,2} = \max(st_{1,1},st_{3,1})$ 转移过来，所以我们有以下递推式：

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

但是这个 $i$ 有不能比 $n$ 大，所以当 $j$ 确定的时候，有 $i \in [1,n-2^j+1]$.

而 $2^j \le n$，所以有 $j \le \log_2 n$.

注意：我们要提前预处理这个数组。

void init(){ll len=log2(n);for(int j=1;j<=len;j++){for(int i=1;i+(1<<j)-1<=n;i++){st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);}}
}

ST 表的最值求法

对于 $\large\max\limits_{i=l}^r a_i$，我们也考虑用 ST 表的思想，通过两个 ST 表直接维护的区间，然后求最值即可。

那么我们将 $[l,r]$ 分为两个子区间，那么一个区间满足 $[l,r]$ 中 ST 表可维护的最大的子区间，也就是满足 $l+2^k-1 \le r$。

解这个不等式，则可以得出 $k \le \log_2 r-l+1$，这里直接令 $k = \log_2 r-l+1$ 即可。所以整个区间就是 $st_{l,k}$

现在只要反着找就可以了，因为对称性，所以 $k = \log_2 r-l+1$。

我们设该区间的起点为 $L$，那么一定满足 $L+2^k-1=r$。

解这个方程，可以知道 $L = r-2^k+1$，所以整个区间就是 $st_{r-2^k+1,k}$.

所以答案就为 $\max(st_{l,k},st_{r-2^k+1,k})$.

所以就可以写出完整代码了。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
ll st[N][25];
ll n,q,k,ans,l,r;ll read(){int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}void init(){ll len=log2(n);for(int j=1;j<=len;j++){for(int i=1;i+(1<<j)-1<=n;i++){st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);}}
}
int main(){n=read();q=read();for(int i=1;i<=n;i++) st[i][0]=read();init();while(q--){l=read(),r=read();k=log2(r-l+1);ans=max(st[l][k],st[r-(1<<k)+1][k]);printf("%lld\n",ans);}return 0;
}

这里我求的是区间最大值。

好了现在我们可以做点题了：