ST表是什么
- ST表其实不叫ST表，因为ST中的T已经是table表的意思了
- ST表适合用来处理RMQ,LCA等经典问题
st[i][j]代表 区间[i,i+2^j-1]st[i][0]=a[i](初始化)
模板题1
每天,你们学校有N(1 <= N <= 50,000)个人按同一序列排队做操. 有一天, 老师让你找一队连续序列的人来进行比赛. 但是为了避免水平悬殊,他们的不应该相差太大. 你准备从Q (1 <= Q <= 200,000) 个可能的选择中选拔，给你所有人的身高 (1 <= 身高 <= 1,000,000). 你需要计算出每一组里面最高和最矮的人的身高差别.
- st表，开两个数组(st和dp)，一个记录个子高的，一个记录个子矮的
- 用两个函数初始化st,dp
st[i][0]=dp[i][0]=a[i](初始化)- c++函数log2():对后面的Q次询问有用
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+5;
int st[N][20], n, q, x, y, lg;
int dp[N][20];
void stm() {
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]);
}
void stn() {
for (int j = 1; (1 << j) <= n; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
}
int main() {
cin >> n>>q;
for (int i = 1; i <= n; i++) cin >> st[i][0];
for (int i = 1; i <= n; i++) dp[i][0]=st[i][0];
stm(),stn();
while (q--){
cin >> x >> y;
lg = (int)log2(y - x + 1),;
cout << max(st[x][lg], st[y - (1 << lg) + 1][lg]) - min(dp[x][lg], dp[y - (1 << lg) + 1][lg]) << endl;
}
return 0;
}
模板题2
- 这是原题网址
- 跟上一题差不多，max/min只留一个max就行了（st和dp只留st)
- 不加快读WA 3个，不加快写也WA 3个，两个都不加WA 6个
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
inline int 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;
}
inline void write(int x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
int st[N][20], n, q, x, y, lg;
void stm() {
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]);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
n = read(), q = read();
for (int i = 1; i <= n; i++) st[i][0] = read();
stm();
while (q--) {
x = read(), y = read();
lg = (int)log2(y - x + 1);
write(max(st[x][lg], st[y - (1 << lg) + 1][lg]));
putchar('\n');
}
return 0;
}
模板题3(RMQ之gcd)
- 把模板题2的max换成__gcd(辗转相除也行)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int st[N][20], n, q, x, y, lg;
void stm() {
for (int j = 1; (1 << j) <= n; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
st[i][j] = __gcd(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
int main() {
cin >> n>>q;
for (int i = 1; i <= n; i++)
cin >> st[i][0];
stm();
while (q--){
cin >> x >> y,;
lg = (int)log2(y - x + 1);
cout << __gcd(st[x][lg], st[y - (1 << lg) + 1][lg]) << endl;
}
return 0;
}