首页 > 代码库 > RMQ的ST算法

RMQ的ST算法

·RMQ的ST算法
    状态设计:
        F[i, j]表示从第i个数起连续2^j个数中的最大值
    状态转移方程(二进制思想):
        F[i, j]=max(F[i,j-1], F[i + 2^(j-1),j-1])
    查询时:
        因为这个区间的长度为j - i + 1,所以我们可以取k=log2( j - i + 1),
        则有:RMQ(A, i, j)=max{F[i , k], F[ j - 2 ^ k + 1, k]}。

RMQ的ST算法