简介RMQ是询问某个区间内的最大值或最小值本文主要讲解RMQ的求解方法——ST算法。ST算法通常用在要多次询问一些区间的最值的问题中。它可以做到O(nlogn)的预处理O(1)回答每个询问。使用ST算法的条件是无修改因此它适用于没有修改并且询问次数较多10^6级别甚至更大的情况。ST表预处理ST算法的原理实际上是动态规划我们用a[1...n]表示一组数。设f[i, j]表示从a[i]到a[i 2^j - 1]这个范围内的最大值也就是以a[i]为起点连续2^j个数的最大值。由于元素个数为2^j个所以从中间平均分成两部分每一部分的元素个数刚好为2^(j-1)个也就是说把f[i, j]分为f[i, j-1]和f[i 2^(j-1), j-1]如下图ST表整个区间的最大值一定是左右两部分最大值的较大值满足动态规划的最优化原理分析得到状态转移方程f[i][j] max(f[i][j - 1], f[i 2^(j-1)][j - 1])边界条件为f[i][0] a[i]这样就可以在O(nlogn)的时间复杂度内预处理f数组。ST表查询若我们要询问区间[li, ri]的最大值则先求出最大的x满足2^x≤ ri - li 1那么区间[li, ri][li, li2^x-1] [ri-2^x1, ri] 如下图所示两个区间的元素个数都为2x所以[li, ri]的最大值为max(f[li][x], f[ri – 2^x 1][x])可以在O(1)内计算出来。虽然这两个区间有交集但是对于求区间最值来说没有影响这就是ST算法只适用于求区间最值的原因。求区间[x,y]最大值直接给出表达式k log2(y - x 1)ans max(f[x][k], f[y - 2k 1][k])参考代码Q1:为何递推算f[i][j]时i的终止点为in-(1j)1,为啥要加1Q2:klog(r-l1)/log(2),因为是取整这样会不会造成遗漏例如N5和N4的k值相同技巧:因为cmath库中的log2函数效率不高所以除了调用log2函数外通常还会使用O(N)递推预处理出1~N这N种区间长度各自对应的k值。具体地设log[d]表示log2d下取整则log[d] log[d/2]1。
RMQ算法与st表
简介RMQ是询问某个区间内的最大值或最小值本文主要讲解RMQ的求解方法——ST算法。ST算法通常用在要多次询问一些区间的最值的问题中。它可以做到O(nlogn)的预处理O(1)回答每个询问。使用ST算法的条件是无修改因此它适用于没有修改并且询问次数较多10^6级别甚至更大的情况。ST表预处理ST算法的原理实际上是动态规划我们用a[1...n]表示一组数。设f[i, j]表示从a[i]到a[i 2^j - 1]这个范围内的最大值也就是以a[i]为起点连续2^j个数的最大值。由于元素个数为2^j个所以从中间平均分成两部分每一部分的元素个数刚好为2^(j-1)个也就是说把f[i, j]分为f[i, j-1]和f[i 2^(j-1), j-1]如下图ST表整个区间的最大值一定是左右两部分最大值的较大值满足动态规划的最优化原理分析得到状态转移方程f[i][j] max(f[i][j - 1], f[i 2^(j-1)][j - 1])边界条件为f[i][0] a[i]这样就可以在O(nlogn)的时间复杂度内预处理f数组。ST表查询若我们要询问区间[li, ri]的最大值则先求出最大的x满足2^x≤ ri - li 1那么区间[li, ri][li, li2^x-1] [ri-2^x1, ri] 如下图所示两个区间的元素个数都为2x所以[li, ri]的最大值为max(f[li][x], f[ri – 2^x 1][x])可以在O(1)内计算出来。虽然这两个区间有交集但是对于求区间最值来说没有影响这就是ST算法只适用于求区间最值的原因。求区间[x,y]最大值直接给出表达式k log2(y - x 1)ans max(f[x][k], f[y - 2k 1][k])参考代码Q1:为何递推算f[i][j]时i的终止点为in-(1j)1,为啥要加1Q2:klog(r-l1)/log(2),因为是取整这样会不会造成遗漏例如N5和N4的k值相同技巧:因为cmath库中的log2函数效率不高所以除了调用log2函数外通常还会使用O(N)递推预处理出1~N这N种区间长度各自对应的k值。具体地设log[d]表示log2d下取整则log[d] log[d/2]1。
