Algorithms Dead Episode 2: RMQ Tricks
Episode 2 of Algorithms Dead is out now! In it, I talk about:
- How to find the min in a range of an array on O(1)
- How to build an RMQ in O(n)
- How to use an RMQ to find the lowest common ancestor in a tree
If you're new to these ideas, or looking for a refresher, it might be worth checking out. If you have questions, feel free to post them below instead of DMing me, so that other people with the same questions can see the answers.
Further Reading
brunomont and tfg showed me their fantastic (and recently published) blog post here: https://codeforces.net/blog/entry/78931. This didn't influence this episode or anything (my stuff was based on jcg's comment on this post from 7 months ago), but brunomont does a great job benchmarking this against segtrees, so definitely go upvote his post for his hard work!
