Algorithms Dead Episode 2: RMQ Tricks↵
==================↵
↵
[Episode 2 of Algorithms Dead](https://youtu.be/GWXf3vVtf-c) 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↵
------------------↵
↵
[user:tfg,2020-06-20] just introduced me to his fantastic (and recently published) blog post here: [https://mirror.codeforces.com/blog/entry/78931](https://mirror.codeforces.com/blog/entry/78931). This didn't influence this episode or anything (my stuff was based on [user:jcg,2020-06-20]'s comment on [this post from 7 months ago](https://mirror.codeforces.com/blog/entry/71706)), but [user:tfg,2020-06-20] does a great job benchmarking this against segtrees, so definitely go upvote his post for his hard work!
==================↵
↵
[Episode 2 of Algorithms Dead](https://youtu.be/GWXf3vVtf-c) 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↵
------------------↵
↵
[user:tfg,2020-06-20] just introduced me to his fantastic (and recently published) blog post here: [https://mirror.codeforces.com/blog/entry/78931](https://mirror.codeforces.com/blog/entry/78931). This didn't influence this episode or anything (my stuff was based on [user:jcg,2020-06-20]'s comment on [this post from 7 months ago](https://mirror.codeforces.com/blog/entry/71706)), but [user:tfg,2020-06-20] does a great job benchmarking this against segtrees, so definitely go upvote his post for his hard work!
