ST表主要用于区间最值操作。更准确的说，应该是用于可重复贡献
比如区间最小值，最大值。
我们先来看一道模板题：
https://www.luogu.com.cn/problem/P3865
1，暴力超时。线段树可行。
2，我们用st表。
我们定义f[N][21];f[i][j]表示的是区间[i,i+(1<<j)-1]这个区间的最大值。
我们可以如何通过小区间来转移得到大区间呢？
我们发现f[i][j]=max(f[i][j-1],f[i+(1<<j)][j-1]);这个两个小区间合起来就是大区间。所以我们可以通过此种方法进行转移，从而得到每个区间的最值
模板如下：
#include"stdio.h"
#include"string.h"
#include"math.h"
#include"algorithm"
using namespace std;
const int N = 100100;
int n,m;
int a[N],f[N][30];///表示的是下标为[i,i + 2^j-1]这个区间最大值
int Logn[N];
void pre() {
Logn[1] = 0;
Logn[2] = 1;
for (int i = 3; i < N; i++) {
Logn[i] = Logn[i / 2] + 1;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i ++)
{
scanf("%d",&a[i]);
f[i][0] = a[i];
}
for(int j = 1; j <= 21; j ++)
{
for(int i = 1;i + (1 << j) - 1 <= n; i ++)
{
f[i][j] = max(f[i][j - 1],f[i + (1 << (j - 1))][j - 1]);
}
}
pre();
while(m -- )
{
int l,r; scanf("%d%d",&l,&r);
int s = Logn[r - l + 1];
int maxx = max(f[l][s],f[r - (1 << s) + 1][s]);
printf("%d
",maxx);
}
}
进阶题：https://www.luogu.com.cn/problem/P2471
本题，我们难点在于分情况进行讨论。而且还很多情况，就很恶心。
唉，心累。
本题结合代码进行讲解或许好些
#include"stdio.h"
#include"string.h"
#include"math.h"
#include"algorithm"
using namespace std;
const int N = 50100;
inline int read() {
char c = getchar();
int x = 0, f = 1;
while (c < '0' || c > '9') {
if (c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
int n,m;
int a[N],f[N][30];///表示的是下标为[i,i + 2^j-1]这个区间最大值
int Logn[N];
int year[N];
void pre() {
Logn[1] = 0;
Logn[2] = 1;
for (int i = 3; i < N; i++) {
Logn[i] = Logn[i / 2] + 1;
}
}
int main()
{
n = read();
for(int i = 1; i <= n; i ++)
{
year[i] = read(); f[i][0] = read();
}
for (int j = 1; j <= 21; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
m = read();
pre();
while(m -- )
{
int l,r;l = read(); r = read();
if(l == r)///如果输入的是相同年份，那一定是true
{
printf("true
");continue;
}
int id1 = lower_bound(year + 1,year + n + 1,l) - year;
int id2 = lower_bound(year + 1,year + n + 1,r) - year;
if(id1 == id2){///如果年份不相同，但是查找下表相同，那我们肯定一定是maybe。这几种情况可以画画就知道了。
printf("maybe
");continue;
}
if(year[id1] == l && year[id2] == r){///l和r都存在的情况
if(f[id1][0] < f[id2][0]) {///如果r的值大于l年份的值，那一定是false。根据题目定义可得。
printf("false
"); continue;
}
if(id1 + 1 == id2){///如果他们之间只相差一个单位
if(r - l + 1 == 2 && f[id2][0] <= f[id1][0]) {///如果r的值小于等于l地方的值，则一定为true。
printf("true
");
} else {
printf("maybe
");
}
continue;
}
int x = id1 + 1,y = id2 - 1;
int s = Logn[y - x + 1];
int maxx = max(f[x][s], f[y - (1 << s) + 1][s]);///查找id1+1，id2-1这个区间的最值。因为+1，-1，的缘故，所以我们在上面就特判了相差一个单位的情况。
if(maxx < f[id2][0]){
if(id2 - id1 + 1 == r - l + 1) printf("true
");
else printf("maybe
");
} else printf("false
");
} else if(year[id1] != l && year[id2] != r){///l和r都不存在的情况
printf("maybe
");
} else if(year[id1] == l){///仅l存在的情况
if(id1 + 1 == id2){
printf("maybe
"); continue;
}
int x = id1 + 1,y = id2 - 1;
int s = Logn[y - x + 1];
int maxx = max(f[x][s], f[y - (1 << s) + 1][s]);
if(f[id1][0] <= maxx) printf("false
");
else printf("maybe
");
continue;
}
else if(year[id2] == r) {///仅r存在的情况
if(id1 + 1 == id2){
if(f[id1][0] < f[id2][0])///这里是个坑点，注意l的值是没有的，id1位置的值是比l大，那么这个值小于r值，那一定是有可能的。这个我没考虑到。
printf("maybe
");
else printf("false
");
continue;
}
int x = id1,y = id2 - 1;
int s = Logn[y - x + 1];
int maxx = max(f[x][s], f[y - (1 << s) + 1][s]);
if(f[id2][0] > maxx) printf("maybe
");
else printf("false
");
}
}
return 0;
}