We study the one-dimensional range minimum query (RMQ) problem in the external memory model. We provide the first space-optimal solution to the batched static version of the problem. On an instance with N elements and Q queries, our solution takes Θ(sort(N + Q)) = Θ( N+QB log M /B N+QB ) I/O complexity and O(N + Q) space, where M is the size of the main memory and B is the block size. This is a factor of O(log M /B N) improvement in space complexity over the previous solutions. We also show that an instance of the batched dynamic RMQ problem with N updates and Q queries can be solved in O ( N+QB log2M/B N+QB ) I/O complexity and O(N + Q) space.
Lecture Notes in Computer Science: 13th International Symposium, Wads 2013, London, On, Canada, August 12-14, 2013. Proceedings, 2013, p. 37-48
International Symposium on Algorithms and Data Structures, 2013