Tags

By year

  1. 2018 (2)
  2. 2017 (4)
  3. 2015 (9)

Some Practice Examples of Range Minimum Query (RMQ)

C++ Algorithm Snippet

Posted on Jul 31


Range Minimum Query (RMQ)

RMQ can be used to query minimum/maximum value in a specified interval with time complexity of \(O(\log n)\).

Templated OO Version

Here is another implementation sample of RMQ in a templated OO style. It may be better if it has the ability to change the min function to max or similar. However, I think that the plain old procedural style is satisfactory in most cases and this kind of generality is not necessary.


2015 My gh-pages