动态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第一题(话说在机房值日的感觉~~爽!)

贴之代码:

题目在这里,点下箭头展开。

原创文章,转载请注明(最好把图片带走): 转载自Comzyh的博客

本文链接地址: 动态RMQ问题(区间最值)的O(LogN)线段树解法–TYVJ1039忠诚2

2 Responses

发表评论