SecondThread's blog

Algorithms Dead Episode 2: RMQ Tricks!
By SecondThread, history, 4 years ago, In English

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://mirror.codeforces.com/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!

  • Vote: I like it
  • +181
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

I added timestamps to the video description, but here they are as well:

  • Sparse tables: 0:25
  • RMQ use cases: 6:30
  • O(1) LCA: 7:30
  • Example Problem of Binary Searching an RMQ: 10:27
  • RMQs in O(n) precomp/memory, O(log(n)) query: 13:30
  • Runtime comparison to Segment Trees: 19:10
  • Handling small range queries on O(1): 20:30
  • When not to use the O(n)/O(1) RMQ: 29:26
→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Auto comment: topic has been updated by SecondThread (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

SecondThread Will it be too much to ask you to add some codeforces practice problem links? :)

→ Reply