Hi Codeforces!

I’ve recorded four videos about Range Minimum Query (RMQ) and related topics. These might be helpful for competitive programmers, especially if you’re diving into data structures or optimization techniques.

Problem statement:

You are given an array $$$a$$$ of size $$$n$$$. You are also given $$$q$$$ queries of type $$$[l, r)$$$ as a range. Each query asks for the minimum element of $$$a$$$ in the given range.

Videos Breakdown:

1. Range Minimum Query / Sqrt Decomposition | Implementation

• Covers fundamentals and basics of RMQ and how sqrt decomposition works.

2. Range Minimum Query / Sparse Table | Implementation

• Explains the sparse table technique step-by-step with code.

3. GSS1 on SPOJ: Sparse Table + Special Node Trick | Implementation

• Solves the classic GSS1 problem using sparse tables and a unique node optimization.

4. The Old Arpa’s Trick Was Wrong! Check This New One. | Implementation

• Most important video! You might know "Arpa’s trick" from this CF blog or CP-Algorithms, but existing explanations are partially incorrect. I explain the flaws, fix the approach, and provide a correct implementation.

⚠️ The order does matter!

Feel free to ask questions in the comments. Happy coding! 🚀