首页 > 代码库 > 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算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。