【学习笔记】ST表

ST 表是一种$O(nlogn)$预处理，查询速度达到$O(1)$的数据结构。上次遇一道题正解本来是$O(nlogn)$的树上倍增，而卡掉$O(nlog^2n)$的树剖 + 线段树。由于只是查询区间最大值，所以可以直接把线段树换成 ST 表，然后就可以凭空优化掉一个$log$，达到比倍增更优的速度。 # 一种对数计算方式 ```cpp int k = (int) (log(n) / log(2)); ``` 虽然会损失精度，但是在取整的时候这点精度也不值一提了。 如果害怕 gg，还可以使用以前用过的递推式，使用时要注意 $log(n) = log2[n]-1$（递推时就已经$+1$，所以要减回去） ```cpp #include<bits/stdc++.h> #define MAXN 100010 using namespace std; int n, m, a; int st[MAXN][40]; int main() { scanf("%d %d", &n, &m); for(int i = 1; i <= n; i++) { scanf("%d", &a); st[i][0] = a; } int k = (int) (log(n) / log(2)); for(int j = 1; j <= k; j++) for(int i = 1; i <= n - (1 << j) + 1; i++) st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]); /// 注意 i, j 枚举顺序，以及 i 的范围 int l, r; while(m--) { scanf("%d %d", &l, &r); int p = (int) (log(r - l + 1) / log(2)); printf("%d\n", max(st[l][p], st[r - (1 << p) + 1][p])); } return 0; } ```