关于静态不修改元素的O(1)查询的RMQ (Range Minimum/Maximum Query)算法区间最大最小值参见我(Comzyh)另一篇文章
先考虑一道题: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(LogN)线段树解法–TYVJ1039忠诚2”