c++st表代码
时间: 2023-08-06 14:11:15 浏览: 60
ST表(Sparse Table)是一种用于求解区间最值问题的数据结构,它可以在 $O(nlogn)$ 预处理,$O(1)$ 查询区间最值。以下是C++实现:
```c++
const int N = 100005;
const int M = 25;
int f[N][M];
int lg2[N];
void init(int n, int a[]) {
lg2[0] = -1;
for (int i = 1; i <= n; i++) {
lg2[i] = lg2[i / 2] + 1;
f[i][0] = a[i];
}
for (int j = 1; j <= lg2[n]; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
}
}
int query(int l, int r) {
int k = lg2[r - l + 1];
return min(f[l][k], f[r - (1 << k) + 1][k]);
}
```
其中,`f[i][j]` 表示以 $i$ 开始、长度为 $2^j$ 的区间内的最小值,`lg2[i]` 表示 $log_2(i)$ 的整数部分。
在初始化时,先预处理出 $2^j$ 的 $j$,然后计算出所有长度为 $1$ 的区间的最小值。接下来,从长度为 $2$ 的区间开始,依次计算出所有长度为 $2^j$ 的区间内的最小值。最终得到的 $f$ 数组即为 ST 表。
在查询时,首先求出 $r - l + 1$ 的整数部分 $k$,然后查询区间 $[l, l + 2^k - 1]$ 和区间 $[r - 2^k + 1, r]$ 的最小值,取两者之间的较小值即为区间 $[l, r]$ 的最小值。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)