RMQ是询问某个区间内的最大值或最小值的问题,ST算法可以求解RMQ问题.ST算法通常用在要 多次询问某一些区间的问题中,相比于线段树,它的程序实现更加简单,运行速度更快,它可以做到O的预处理,O回答每个问题.使用ST算法的条件是没有修改操作,因此它适用于
ST算法是用于解决RMQ问题的一种著名算法。ST算法能在复杂度为\的预处理后，以\的复杂度在线处理序列区间内的最大值/最小值。值得注意的是，ST算法并不能处理需要修改点权的区间最值问题。ST表的实现同样依据倍增思想，设\表示序列下标区间为\的最值，即从\(
RMQ，即区间最值查询，是指这样一个问题：对于长度为n的数列A，回答若干询问RMQ，返回数列A中下标在i，j之间的最小/大值。这两个问题是在实际应用中经常遇到的问题，下面介绍一下解决这两种问题的比较高效的算法。当然，该问题也可以用线段树解决，算法复杂度为：
安科网(Ancii)，中国第一极客网
Copyright © 2013 - 2019 Ancii.com
京ICP备18063983号-5 京公网安备11010802014868号