On (Dynamic) Range Minimum Queries in External Memory

摘要

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+Q)/B) log_(M/B) ((N+Q)/B)) 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+Q)/B) log~2_(M/B) ((N+Q)/B)) I/O complexity and O(N + Q) space.