ST表，听起来高大上，实际上限制非常多，仅仅可以求最值问题；
为什么？先从原理看起；
st表运用了倍增的思想：st[i][j] = min(st[i][j - 1],st[i + 2^(j - 1))][j - 1])；
意义是：从i开始向后连续2^j个位置的最大值是，i开始向后连续2^(j-1)个位置的最大值和i+2^(j-1)开始向后连续2^(j-1)个位置的最大值；
好了，结构建立起来了，那么怎么查询呢？
一个公式：2^log(a)>a/2 。
所以说，查询(x,y)时我们设k=log(y-x+1);
ans=max(f[x][k],f[y-(1<<k)+1][k]);
现在我们知道了，ST表只能求最值的原因是它在查询时，为了节约时间复杂度而导致查询区间取并集操作；这样求区间和便无法得到正确答案；
附：1.求一维ST最值：
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[100010];
int f[100010][40],g[100010][40];
int n,q;
void build()
{
for(register int i=1;i<=n;i++){
f[i][0]=a[i];
g[i][0]=a[i];
}
for(register int j=1;(1<<j)<=n;j++){
for(register int i=1;(i+(1<<j)-1)<=n;i++){
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
g[i][j]=min(g[i][j-1],g[i+(1<<(j-1))][j-1]);
}
}
}
int query(int x,int y)
{
int tmp=log2(y-x+1);
return max(f[x][tmp],f[y-(1<<tmp)+1][tmp])-min(g[x][tmp],g[y-(1<<tmp)+1][tmp]);
}
signed main()
{
scanf("%lld%lld",&n,&q);
for(register int i=1;i<=n;i++) scanf("%lld",&a[i]);
build();
for(register int i=1;i<=q;i++){
int x,y;
scanf("%lld%lld",&x,&y);
printf("%lld
",query(x,y));
}
}
而二维st表原理就是将一个正方形分成了4份：
令 st[i][j][k]表示左上角为i，j，边长为k的正方形中的最大值。
st[i][j][k]=Max(st[i][j][k-1],st[i+(1<<k-1)][j][k-1],st[i][j+(1<<k-1)][k-1],st[i+(1<<k-1)][j+(1<<k-1)][k-1]);
查询时与一维ST表类似，取并集操作；
#include <bits/stdc++.h>
#define inc(i,a,b) for(register int i=a;i<=b;i++)
using namespace std;
int a,b,n;
int mmap[1001][1001];
int f[1001][1001][8],g[1010][1010][8];
void build()
{
inc(i,1,a){
inc(j,1,b){
f[i][j][0]=mmap[i][j];
g[i][j][0]=mmap[i][j];
}
}
for(int k=1;k<=7;k++){
for(int i=1;i+(1<<k)-1<=a;i++){
for(int j=1;j+(1<<k)-1<=b;j++){
f[i][j][k]=max(f[i+(1<<k-1)][j+(1<<k-1)][k-1],f[i+(1<<k-1)][j][k-1]);
f[i][j][k]=max(f[i][j][k],f[i][j+(1<<k-1)][k-1]);
f[i][j][k]=max(f[i][j][k],f[i][j][k-1]);
g[i][j][k]=min(g[i+(1<<k-1)][j+(1<<k-1)][k-1],g[i+(1<<k-1)][j][k-1]);
g[i][j][k]=min(g[i][j][k],g[i][j+(1<<k-1)][k-1]);
g[i][j][k]=min(g[i][j][k],g[i][j][k-1]);
}
}
}
}
int query(int x,int y,int goal)
{
long long tmp1=max(f[x][y][goal],f[x+n-(1<<goal)][y][goal]);
long long tmp2=max(f[x][y+n-(1<<goal)][goal],f[x+n-(1<<goal)][y+n-(1<<goal)][goal]);
long long tmp3=max(tmp1,tmp2);
long long tmp4=min(g[x][y][goal],g[x+n-(1<<goal)][y][goal]);
long long tmp5=min(g[x][y+n-(1<<goal)][goal],g[x+n-(1<<goal)][y+n-(1<<goal)][goal]);
long long tmp6=min(tmp4,tmp5);
return tmp3-tmp6;
}
signed main()
{
scanf("%d%d%d",&a,&b,&n);
inc(i,1,a){
inc(j,1,b){
scanf("%d",&mmap[i][j]);
}
}
build();
int goal=log2(n);
int ans=INT_MAX;
inc(i,1,a-n+1){
inc(j,1,b-n+1){
ans=min(ans,query(i,j,goal));
}
}
cout<<ans;
}
在做一维和二维ST表的时候，我们可以自己推出：三维的ST表，甚至于四维的ST表；只不过由于他们的时间复杂度较高，内存需求较大，我们便不再需要他们了。但这种思维可以运用到别的地方。