标签： 动态规划

RMQ(range minimum/maximum query)问题

给定一组数，给定给定一个区间，求区间最值，算法大致有以下几种

1. O(n)算法,直接扫描一遍区间,求最值.
   优点:编程简单,可动态求解(数组可动态更改)
   缺点:不能处理大量数据.
2. 使用线段树,可以优化成Log(N)
   优点:时间复杂度低,更改操作复杂度低
   缺点:编程复杂度大.
3. 预处理O(N log N),查询O(1)的Sparse_Table(稀疏表)算法
   优点:编程简单,可动态求解(数组可动态更改)
   缺点:没啥,基本算法不能处理动态更改，改进后可以更改(复杂度貌似不小，大于LogN).
4. 快速选择法 Quick Slect(打酱油的,不是RMQ)，能在O(N) (我估算是1.5N)的时间内得到区间第K大/小值

下面主要介绍ST算法
Continue reading “用于求区间最值(RMQ问题)的O(1)算法–ST(稀疏表)算法”