RMQ

动态RMQ问题(区间最值)的O(LogN)线段树解法–TYVJ1039忠诚2

关于静态不修改元素的O(1)查询的RMQ (Range Minimum/Maximum Query)算法区间最大最小值参见我(Comzyh)另一篇文章

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

先考虑一道题:TYVJ1039 忠诚2 (看不了的本文末尾有题)

话说TYVJ总是喜欢出这么赤裸裸的算法题,我也喜欢。

很显然 m(m<=100000)笔账,n表示有n个问题,n<=100000 \( \Theta ( N^{2})\)的算法必然是不行的

话说ST(Sparse Table)算法不是查询O(1)么?ST算法的结构表明,ST的查询复杂度永远是O(1)的,但是动态修改基本上每次是O(NlogN)小点的,对于小更新量还可以,大量修改就不行了,事实证明,我写的动态ST算法超时3点。

这时,线段树的修改(Log N)优势就体现出来了。(因为本题更新的是,比较特殊,是logN)

修改(Insert)时由顶而下以类似二分的方法找到最下面,然后回溯,比较刚更新的点与另一子树,求Min,更新为当前线段的Min值
这个模型比染色用的线段树简单多了,于是它成了我线段树AC第一题(话说在机房值日的感觉~~爽!)

贴之代码:
Continue reading

用于求区间最值(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