ST表

定义

用于求解静态RMQ问题

主要操作

初始化

1 void STPrework(){
2     for(int i = 1;i <= n;i++) f[i][0] = A[i];
3     for(int j = 1;(1 << j) <= n;j++)
4         for(int i = 1;i + (1 << j) - 1 <= n;i++)
5             f[i][j] = max(f[i][j - 1],f[i + (1 << j - 1)][j - 1]);
6 }

查询

1 int STQuery(int l,int r){
2     int k = 0;
3     while((1 << k + 1) < r - l + 1) k++;
4     return std::max(f[l][k],f[r - (1 << k) + 1][k]);
5 }

时间及空间复杂度

时间复杂度

初始化为$O(n\log n)$

查询为$O(1)$

空间复杂度

$O(n)$

模板

 1 const int MAXN = 100000 + 6;
 2 int f[MAXN][66],A[MAXN],n,m;
 3 
 4 void STPrework(){
 5     for(int i = 1;i <= n;i++) f[i][0] = A[i];
 6     for(int j = 1;(1 << j) <= n;j++)
 7         for(int i = 1;i + (1 << j) - 1 <= n;i++)
 8             f[i][j] = max(f[i][j - 1],f[i + (1 << j - 1)][j - 1]);
 9 }
10  
11 int STQuery(int l,int r){
12     int k = 0;
13     while((1 << k + 1) < r - l + 1) k++;
14     return std::max(f[l][k],f[r - (1 << k) + 1][k]);
15 }