ST表

ST表原理及实现：https://www.cnblogs.com/qq965921539/p/9608980.html

ST表是通过离线预处理出子区间$[l,r]$的最值。其中$st[i][j]$代表的是子区间$[i,i+2^j-1]$的最值。

预处理的效率是$O(nlogn)$，查询的效率是$O(1)$。

实现：

预处理：

 1 int a[N];//原始输入数组
 2 int st[N][k];//st表   k=log2(n)
 3 
 4 void init(int n){
 5     for (int i = 0; i < n; i++)
 6         st[i][0] = a[i];
 7 
 8     for (int j = 1; (1 << j) <= n; j++){
 9         for (int i = 0; i + (1 << j) - 1 < n; i++)
10             st[i][j] = min(st[i][j - 1],st[i + (1 << (j - 1))][j - 1]);
11     }
12 }

查询：

1 int search(int l, int r){
2      int k = (int)(log((double)(r - l + 1)) / log(2.0));
3      return min(st[l][k],st[r - (1 << k) + 1][k]);
4 }