4 ms·
The range minimum query problem (RMQ) used to solve LCA is a really fun one. I spend two lectures on it in my advanced data structures course. The approach cove
by htiek 7mo ago
The range minimum query problem (RMQ) used to solve LCA is a really fun one. I spend two lectures on it in my advanced data structures course. The approach covered in the slides linked here is perhaps the best-known way to solve LCA via RMQ, but I personally prefer one developed by Fischer and Heun in 2006. Check the first two lectures of my course (https://web.stanford.edu/class/archive/cs/cs166/cs166.1256/ https://web.stanford.edu/class/archive/cs/cs166/cs166.1256/) for details.
- emil-lp 7mo agoRange minimum query? Isn't that just prefix sum and a queue?
- barishnamazov 7mo agoYou are probably confusing it with a sliding window problem. RMQ [0] is about finding the minimum value in given arbitrary subarray. [0] https://en.wikipedia.org/wiki/Range_minimum_query https://en.wikipedia.org/wiki/Range_minimum_query
- emil-lp 7mo agoYou are right! That's interesting!
- remywang 7mo agoThanks a lot for the wonderful slides, I used them to learn suffix arrays!