Monday, May 18, 2009
Range minimum queries and LCA
Range Minimum Query (RMQ) is used on arrays to find the position of an element with the minimum value between two specified indices. There is a trivial quadratic solution based on dynamic programming. I found this tutorial complete and useful. Many other solutions exist. In particular, I appreciated the one based on Segment Trees. A bookmark, and I plan to revisit it soon.
Pubblicato da codingplayground a 6:47 AM