# ST 表是什么
ST 表是一个用来解决区间最值问题查询的算法
它用 O (nlogn) 复杂度预处理，可以实现 O (1) 复杂度的查询。
缺点：无法支持在线修改
模板题：ST 表 - 洛谷
# 1. 预处理
用一个二维数组 dp [i][j] 表示下标为 i ~ i + 2j - 1 的最值（最大 or 最小值）
则
①易知边界条件 dp [i][0] 为 a [i]，既 i~i 的最大值为其本身
②接下来是状态转移方程，如图
# 1 << j 相当于 2j
初始化代码
void init(int n) { | |
for (int i = 0; i < n; i++) { | |
dp[i][0] = a[i]; | |
} | |
for (int j = 1; (1<<j) <= n; j++) { | |
for (int i = 0; i + (1<<j) <= n; i++) { | |
dp[i][j] = max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]); | |
} | |
} | |
} |
# 2. 查询
接下来就是查询，因为每次给出的查询区间长度不一定恰好为 2^j，所以我们需要以下定理:（参考大佬证明）
# 2log(a)>a/2
# log (a) 表示小于等于 a 的 2 的最大几次方
# eg:log(4)=2,log(5)=2,log(6)=2,log(7)=2,log(8)=3,log(9)=3……
若我们要查询 a~b 区间的最小值
首先我们求出区间长度 len = b-a+1 并令 t = log(len)
由上述定理，2t>len/2
也就是说，2^t 在 a,b 区间的右半边
a,b 的最小值，即为 min（a ~ (a+2t-1), (b-2t+1) ~ t）如图
查询代码：
ll sol(int a, int b) { | |
int t = (int) (log(b-a+1.0)/log(2.0)); | |
return max(dp[a][t], dp[b-(1<<t)+1][t]); | |
} |
# 3. 完整代码
题目：ST 表 - 洛谷
开了 O2 优化和快读才能 ac
#include <iostream> | |
#include <algorithm> | |
#include <cmath> | |
using namespace std; | |
const int maxn = 100000; | |
typedef long long ll; | |
ll a[maxn]; | |
ll dp[maxn][25];// 此处以最大值为例 | |
void init(int n) { | |
for (int i = 0; i < n; i++) { | |
dp[i][0] = a[i]; | |
} | |
for (int j = 1; (1<<j) <= n; j++) { | |
for (int i = 0; i + (1<<j) <= n; i++) { | |
dp[i][j] = max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]); | |
} | |
} | |
} | |
ll sol(int a, int b) { | |
int t = (int) (log(b-a+1.0)/log(2.0)); | |
return max(dp[a][t], dp[b-(1<<t)+1][t]); | |
} | |
int main() { | |
ios::sync_with_stdio(false); | |
int n,m; | |
cin >> n >> m; | |
for (int i = 0; i < n; i++) { | |
cin >> a[i]; | |
} | |
init(n); | |
while(m--) { | |
int x,y; | |
cin >> x >> y; | |
cout << sol(x-1,y-1) << endl; | |
} | |
return 0; | |
} |
