Solving RMQ Problems

Range Minimum Queries (RMQ) and similar type of problems could be solved by many data structures.

Sparse Table is one such data structure. Generally at my level Sparse Table or Segment Tree is all I will need for these problems. So the advance structures could be saved for later when I am better.

Sparse Table can only answer idempotent function over range in $O(1)$ and not all associative functions.

Advance Articles

• Topcoder: Range minimum query and lowest common ancestor
  • Basics of solving RMQ with different data structures and the comparisons between them
  • Sparse Table intro
  • Converting LCA to RMQ with tree traversal
  • From RMQ to LCA with Cartesian tree and applying Farach-Colton and Bender Algorithm
    • It may lead to < O(N), O(1) > complexity in theory, but practical performance is bad due to constant factor - reference
• YouTube : Algorithms Dead 2: RMQ Tricks
  • Nice introductory and advance tricks
  • Explains how to achieve < O(N), O(1) > for Sparse Table
• Codeforces: Range minimum query in O(1) with linear time construction
  • Explains how to achieve < O(N), O(1) > for Sparse Table with implementation
  • Benchmarking this implementation against other DS
• Codeforces : Sqrt-tree: answering queries in O(1) with O(NloglogN) preprocessing
  • Different data structure for solving RMQ problem
  • Good read
• Codeforces : Range Minimum Query(O(N),O(1))
• YouTube : Episode 28 - Sparse Tables and LCA by Algorithms Live
• Arpa’s Trick
  • Solving RMQ problem using DSU

Problems

• SPOJ - DISQUERY
  • Calculate something in the path from u to v
• CodeChef - TALCA
  • Change the root of the tree and find new LCA

Practice

• cp-algorithms
• LCA Problems