Rendered at 11:34:18 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
jihadjihad 21 hours ago [-]
OT, but as a kid I remember being perpetually confused whenever "least common multiple" or "least common denominator" came up in math class. I always parsed them as "least common", so "rarest", which of course didn't make any sense.
Maybe the takeaway is that I was born to be a programmer, and this was my fifth grade version of the old joke where the programmer's wife asks him to "get a gallon of milk, and if they have eggs, get a dozen."
htiek 22 hours 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/) for details.
remywang 20 hours ago [-]
Thanks a lot for the wonderful slides, I used them to learn suffix arrays!
emil-lp 22 hours ago [-]
Range minimum query? Isn't that just prefix sum and a queue?
barishnamazov 21 hours ago [-]
You are probably confusing it with a sliding window problem. RMQ [0] is about finding the minimum value in given arbitrary subarray.
Maybe the takeaway is that I was born to be a programmer, and this was my fifth grade version of the old joke where the programmer's wife asks him to "get a gallon of milk, and if they have eggs, get a dozen."
[0] https://en.wikipedia.org/wiki/Range_minimum_query
A preprint of the paper is available here: https://web.archive.org/web/20250708141740/https://www.ics.u...