±1 RMQ

缘起

【1】和【2】分别给出了RMQ问题的ST解法（本质就是打表DP）和线段树解法. 这里给出±1RMQ问题的O(N)~O(1)解法. 即算法初始化要 O(N)， 而解答每次询问都只需要O(1)的时间（很快）

这种±1 RMQ 问题的应用场景是什么? 在RMQ的标准解法——O(n)转笛卡尔树， 最后转该树上的LCA问题中有用.

Read More