NlogN

用于求区间最值(RMQ问题)的O(1)算法–ST(稀疏表)算法

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

P156 吞噬比赛 NlogN最长不下降子序列

MY CODE:

Continue reading