ST表 | Kyons'Blog 




 
 
 
 



 
 



ST表

引例

洛谷P3865
$RMQ$的中文翻译为:静态区间最值查询.英文我不知道所以不写给你$n$个数,$m$次查询,查询的内容为区间$[l,r]$中的最大值.
$RMQ$有解法蛮多的,$st$表,线段树,树状数组,划分树都可以做.
$st$表的复杂度为预处理$O(n*{\log_2} n)$+查询$O(m)$
而线段树则需要预处理$O(n*{\log_2} n)$+查询$O(m*{\log_2} n)$
树状数组没学,不清楚
线段树可以看我之前的博客.

定义

这个算法就是基于$DP$和位运算符,我们用$dp[i][j]$表示从第 $i$ 位开始,到第 $i + 2^j -1$ 位的最大值或者最小值。

那么我求$dp[i][j]$的时候可以把它分成两部分,第一部分从 $i$ 到 $i + 2 ^{(j-1)} - 1$ ,第二部分从 $i + 2 ^{(j-1)}$ 到$i + 2^j- 1$,那么可以得到
$$dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1])$$
当$j=0$时,求的是长度为1的区间的最小值,
$j=1$时,求的是长度为2的区间最小值
$j=2$时,求的是长度为4的区间最小值
以此类推,故可在$O(n\log_2 n)$的复杂度处理完.
如图所示
1
查询的话,只需要反过来就阔以了.

完整代码

这里mm[i] = mm[i - 1] +((i&(i - 1)) == 0);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
```cpp
const int MAXN = 1e5 + 10;

int dp[MAXN][31],a[MAXN],mm[MAXN];

void initRMQ(int n)
{
mm[0] = -1;
for (int i = 1; i <= n; i++) {
mm[i] = mm[i - 1] +((i&(i - 1)) == 0);
dp[i][0] = a[i];
}
for (int j = 1; j <= mm[n]; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
}

int rmq(int x, int y)
{
int k = mm[y - x + 1];
return max(dp[x][k], dp[y - (1 << k) + 1][k]);
}

int main()
{
int n,m;
cin >> n >> m;//scanf("%d", &n);
for (int i = 1; i <= n; i++)
cin >> a[i];

initRMQ(n);

while (m--) {
int x, y;
cin >> x >> y;
cout << rmq(x, y) << '\n';
}
return 0;
}

二维st表

暂存
https://blog.csdn.net/VictoryCzt/article/details/83684082

约束RMQ

https://www.cnblogs.com/ghostcai/p/9280720.html
https://blog.csdn.net/VictoryCzt/article/details/83348579

练习题目

洛谷P2251
裸的$RMQ$问题
洛谷P3865
$st$表模板题目
洛谷P2048
$st$表+前缀和+贪心+堆优化


 


 
 
 





 

 


 


 

 

 

 

 
 

 

 

 //删除Valine核心代码库外链调用 //调用刚下载的本地文件以加速加载速度 //这里改为从本地加载