Re:The LCA problem revisited [pdf]
by htiek on Monday March 23, 2026 @09:41AM
(#47489424)
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/) for details.
[ Parent
| on HN ]
Thanks a lot for the wonderful slides, I used them to learn suffix arrays!
Range minimum query? Isn't that just prefix sum and a queue?
Re:The LCA problem revisited [pdf]
by barishnamazov on Monday March 23, 2026 @10:25AM
(#47490013)
You are probably confusing it with a sliding window problem. RMQ [0] is about finding the minimum value in given arbitrary subarray.