@inproceedings{sitchinava-wads13,
  author = "Lars Arge and Johannes Fischer and Peter Sanders and Nodari Sitchinava",
  title  = "On (dynamic) range minimum queries in external memory", 
  booktitle = "Proceedings of the 13th International Symposium on Algorithms and Data Structures",
  series = "WADS '13", 
  pages = "37-48",
  year = 2013,
  month = 8,
  doi = "10.1007/978-3-642-40104-6_4",
  abstract = " 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 $\Theta(\mathrm{sort}(N+Q)) = \Theta(\frac{N+Q}{B}\log_{M/B}
\frac{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 {\em dynamic} RMQ
problem with $N$ updates and $Q$ queries can be solved in $O(\frac{N+Q}{B}
\log^2_{M/B} \frac{N+Q}{B})$ I/O complexity and $O(N+Q)$ space."
}