这是一个创建于 1974 天前的主题，其中的信息可能已经有所发展或是发生改变。
（算法的目的是求区间最值）
RMQ 算法全称为(Range Minimum/Maximum Query)意思是给你一个长度为 n 的数组 A,求出给定区间的最值的下标。当然我们可以采用枚举，但是我们也可以使用线段树来优化，复杂度为(nlogn)，但是最好的办法是采用Sparse_Table 算法，简称 ST 算法。它能在进行(nlogn)的预处理后达到 n(1)的效率。
网上找了一圈教程，好像都没有理解透
希望您能帮助本蒟蒻一下
直接甩博客链接也是可以的，但请不要甩百度出来的前几条链接，因为我都看过了
谢谢
 |
1
litmxs 2019-06-29 15:12:00 +08:00 via Android
对于长度为 n 的数组 A，建立一个 n*logn 大小的表格，st[i][j]代表区间 A[i]到 A[i+2^j]中的最值
例如求区间 10-20 的最值，我们将区间长度 11 分解为 2 的整数次幂相加（ 8+2+1 ），要知道整个区间最值，我们可以查找这三个子区间 10-17，18-19，20-20，也就是 st[10][3]，st[19][1]，st[20][0]，这样查询的复杂度就是 log 而建立 st 表的时候利用 st[i][0]=A[i]和 st[i][j]=st[i][j-1]+st[i+2^(j-1)]两个方程建立，复杂度 nlogn，也就是表的大小 |
|
2
litmxs 2019-06-29 15:19:22 +08:00 via Android
不对，查询的方式我记错了，由于是查询区间最值，查询的子区间可以重合，所以只需要查找 st[10][3]和 st[13][3]，也就是小于区间长度的最大 2 的整数次幂长度的两个子区间，复杂度 O （ 1 ）
|
 |
3
zqqian 2019-06-29 16:35:06 +08:00 via iPhone
|
Select Language