News for hackers. Stuff that matters.
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.
Re:The LCA problem revisited [pdf] by remywang on Monday March 23, 2026 @11:35AM (#47490944)
Thanks a lot for the wonderful slides, I used them to learn suffix arrays!
Re:The LCA problem revisited [pdf] by emil-lp on Monday March 23, 2026 @09:46AM (#47489486)
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.

[0] https://en.wikipedia.org/wiki/Range_minimum_query

Re:The LCA problem revisited [pdf] by emil-lp on Monday March 23, 2026 @11:32AM (#47490905)
You are right! That's interesting!