Prologue

The most commonly known algorithm for RMQ relies on the RMQ problem. It's tedious to program and doesn't perform well in practice. Here introduces a new algorithm which is easy to implement and more efficient.

I learnt the algorithm in Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays.

Main Idea

As the commonly known one, the algorithm works under the framework of "The Method of Four Russians". That is, it divides the array (of size ) into blocks of size , and it processes the queries with at most sub-queries: one inter-block query (of size ) and two intra-block queries (of size ).

Here comes the key observation of the algorithm: the result of the intra-block RMQ queries depend only on the shape of the block Cartersian Tree, and the number of distinct Cartersian trees of size is , which is the Catalan number . Using Stirling's approximation, we know that . Thus, if we have , processing all distinct Cartersian trees takes , while preprocessing the inter-block part using Sparse Table runs in .

Implementation Detail

To implement, the non-trivial part is to partition the blocks into equivalent classes (up to the shape of its Cartersian tree). The method described in the cited paper is to encode Cartersian tree into an integer between and . However, it isn't a must. Under the spirit of one of my recently set problem, we can circumvent the need to encode the Cartersian tree in an obscure way.

Recall that two arrays and have the same Cartersian tree if and only if while and can be computed incrementally. To group by equivalent relationship, we compute for all blocks simultaneously. For two blocks and , if at some step , the Cartersian tree of the two blocks differs. Thus, we perform an radix sort for at each step . A careful implementation runs in linear time.