ST算法解决RMQ问题。
RMQ问题就是区间查询问题,以往的时候是用线段树来做,但是线段树的查询也只是简化到了O(logn)的复杂度,本文要介绍的ST算法,虽然说预处理达到了O(nlogn)的复杂度,但是查询只需要O(1)。ST算法本身是个DP解法。
引例POJ - 3264
题意
给你一个数组,每次询问你某一段区间内的最大值和最小值的差值。
思路
典型的一维RMQ问题。
设置$dp[i,j]$ 代表从第$i$个元素开始连续$2^j$个值的最大值,很明显有$dp[i,0] = 0$.
为了求$f[i,j]$,我们把f[i,j]平均分成两段,每段的元素的个数为$2 ^ {j - 1}$, 所以第一段为 $i$ 到 $i + 2 ^{j -1}- 1$ ,下一段是$ i + 2 ^{j - 1}$ 到 $j$.
dp方程的状态转移方程就是$$dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]]$$
当我们查询的时候,设置$k = log_2(r - l + 1)$, 返回$max(dp[l][k],dp[r - 2^k + 1][k])$
我们需要知道的是我们不怕括号内的两段空间有重复,只是怕可能会超出$l - r的界限$。
因此我们设定$2^k <= r - l + 1$ ,因为我们假设的是这个区间有$k$个元素,所以就会出来上面的$k$的表达式了。
1 |
|