ST 表

· · 算法·理论

什么是 ST 表？

ST 表是一种能快速求出区间内的最小/最大值的数据结构。

怎么实现 ST 表？

以 P3865 为例。设 st_{i,j} 表示从 a_i 开始的 2^j 个数中的最大值。显然 a_i=st_{i,0}。则我们可以用 \mathcal O(n\log n) 的复杂度预处理出 st 数组，然后每次用 \mathcal O(1) 的复杂度实现查询操作。

预处理

我们在算 st_{i,j} 时，可以将两个小区间的答案合并，即

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

代码如下，注意边界条件。

for(int j=1;(1<<j)<=n;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 表，仍应该考虑类似处理 ST 表的方法，将该区间分成两个 ST 表可直接维护的小区间，然后二者求最值即可。为了方便，以下称 k=\log r-l+1。

\max\limits_{l \le i \le r}\{a_i\}=\max(st_{l,k},st_{r-2^k+1,k})

代码如下：

int query(int l,int r) {
  int k=lg[r-l+1];
  return max(st[l][k],st[r-(1<<k)+1][k]);
}

完整的 ST 表代码如下：（lg_i 表示 \log_2i）

#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=100005;
int st[MAXN][25],lg[MAXN];
int query(int l,int r) {
  int k=lg[r-l+1];
  return max(st[l][k],st[r-(1<<k)+1][k]);
}
int main() {
  int n,m;
  scanf("%d %d",&n,&m);
  lg[0]=-1;
  for(int i=1;i<=n;i++) {
    scanf("%d",&st[i][0]);
    lg[i]=lg[(i>>1)]+1;
  }
  for(int j=1;(1<<j)<=n;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]);
  }
  for(int i=1,l,r;i<=m;i++) {
    scanf("%d %d",&l,&r);
    printf("%d\n",query(l,r));
  }
  return 0;
}

例题讲解

P2880 [USACO07JAN] Balanced Lineup G

这是一个标准的 ST 表的问题。我们可以建立两个 ST 表，一个存最大值，另一个存最小值。对于每次询问拿最大值减最小值即可。代码如下：

#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=50005;
int st1[MAXN][25],st2[MAXN][25],lg[MAXN];
int query1(int l,int r) {
  int k=lg[r-l+1];
  return max(st1[l][k],st1[r-(1<<k)+1][k]);
}
int query2(int l,int r) {
  int k=lg[r-l+1];
  return min(st2[l][k],st2[r-(1<<k)+1][k]);
}
int main() {
  int n,q;
  scanf("%d %d",&n,&q);
  lg[0]=-1;
  for(int i=1;i<=n;i++) {
    scanf("%d",&st1[i][0]);
    st2[i][0]=st1[i][0];
    lg[i]=lg[(i>>1)]+1;
  }
  for(int j=1;(1<<j)<=n;j++) {
    for(int i=1;i+(1<<j)-1<=n;i++)
      st1[i][j]=max(st1[i][j-1],st1[i+(1<<j-1)][j-1]);
  }
  for(int j=1;(1<<j)<=n;j++) {
    for(int i=1;i+(1<<j)-1<=n;i++)
      st2[i][j]=min(st2[i][j-1],st2[i+(1<<j-1)][j-1]);
  }
  for(int i=1,l,r;i<=q;i++) {
    scanf("%d %d",&l,&r);
    printf("%d\n",query1(l,r)-query2(l,r));
  }
  return 0;
}

P2866 [USACO06NOV] Bad Hair Day S

这题正解是单调栈，但也可以用 ST 表来做。

对于一个 i，如果 j(j>i) 满足条件，则所有的 x(i<x<j) 也满足条件。因此考虑二分。只要 a_{l-1} 比 \left[l,r\right] 区间中的最大值大，这个区间就是符合条件的。我们用 ST 表来计算 \max\limits_{l \le i \le r}\{a_i\}。代码如下，注意开 long long。

#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=80005;
int st[MAXN][25],lg[MAXN];
int query(int l,int r) {
  int k=lg[r-l+1];
  return max(st[l][k],st[r-(1<<k)+1][k]);
}
bool check(int l,int r) {
  if(l>r)
    return false;
  return (query(l,r)<st[l-1][0]);
}
int main() {
  int n;
  scanf("%d",&n);
  lg[0]=-1;
  for(int i=1;i<=n;i++) {
    scanf("%d",&st[i][0]);
    lg[i]=lg[(i>>1)]+1;
  }
  for(int j=1;(1<<j)<=n;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]);
  }
  long long ans=0;
  for(int i=1;i<=n;i++) {
    int l=i,r=n;
    while(l<r) {
      int mid=(l+r+1)/2;
      if(check(i+1,mid))
        l=mid;
      else
        r=mid-1;
    }
    ans+=l-i;
  }
  printf("%lld",ans);
  return 0;
}