求大佬讲解一下「倍增 RMQ」算法

[MinecraftFuns]

（算法的目的是求区间最值）

RMQ 算法全称为(Range Minimum/Maximum Query)意思是给你一个长度为 n 的数组 A,求出给定区间的最值的下标。当然我们可以采用枚举，但是我们也可以使用线段树来优化，复杂度为(nlogn)，但是最好的办法是采用Sparse_Table 算法，简称 ST 算法。它能在进行(nlogn)的预处理后达到 n(1)的效率。

网上找了一圈教程，好像都没有理解透

希望您能帮助本蒟蒻一下

直接甩博客链接也是可以的，但请不要甩百度出来的前几条链接，因为我都看过了

谢谢

[litmxs]

对于长度为 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，也就是表的大小

[litmxs]

不对，查询的方式我记错了，由于是查询区间最值，查询的子区间可以重合，所以只需要查找 st[10][3]和 st[13][3]，也就是小于区间长度的最大 2 的整数次幂长度的两个子区间，复杂度 O （ 1 ）

[zqqian]

可以看看我的理解

https://www.q-cs.cn/2017/08/09/the-rmq-algorithm-which-based-on-st-table/