RMQ : Preprocessing O(N), Query O(1).

general
, ,
1

Can Someone please provide a detailed explaination for this Algorithm :

RMQ : Preprocessing O(N), Query O(1)

Or a link to detailed explaination of above algo(other than above).

2

The references of that article can help you. If you want something even more detailed, here’s the original article of Bender and Farach-Colton algorithm (provides a lot of theory but no implementation). I haven’t googled for an implementation but maybe an implementation can help you understand it better.

3

Implementation: https://gist.github.com/FallAndRise/34fdc7795eb18fe90f63a9198e1d8505

It’s self explanatory.
Working example: mk3ocX - Online C++0x Compiler & Debugging Tool - Ideone.com