@inproceedings{sitchinava-swat14,
  author = "Peyman Afshani and Nodari Sitchinava",
  title  = "{I/O}-efficient range minima queries",
  booktitle = "Proceedings of the 14th Scandinavian Symposium and Workshops on Algorithm Theory",
  series = "SWAT '14", 
  pages = "1-12",
  year = 2014,
  month = 7,
  doi = "10.1007/978-3-319-08404-6_1",
  abstract = " In this paper we study the \emph{offline (batched) range minima query (RMQ)} problem in the external memory (EM) and cache-oblivious (CO) models. In the \emph{static} RMQ problem, given an array $A$, a query \textsc{rmq}$_A(i,j)$ returns the smallest element in the range $A[i,j]$. 

If $B$ is the size of the block and $m$ is the number of blocks that fit in the internal memory in the EM and CO models, we show that $Q$ range minima queries on an array of size $N$ can be answered in $O(\frac{N}{B} +
\frac{Q}{B}\log_{m} \frac{Q}{B}) = O(\mathrm{scan}(N) + \mathrm{sort}(Q))$  I/Os in the CO model and slightly better $O(\mathrm{scan}(N) + \frac{Q}{B} \log_m \min\{\frac{Q}{B}, \frac{N}{B}\})$ I/Os in the EM model and linear space in both models. Our cache-oblivious result is new and our external memory result is an improvement of the previously known bound.  We also show that the EM bound is tight by proving a matching lower bound.  Our lower bound holds even if the queries are presorted in any predefined order.

In the batched \emph{dynamic} RMQ problem, the queries must be answered in the presence of the updates (insertions/deletions) to the array. We show that in the EM model we can solve this problem in $O(\mathrm{sort}(N) + \mathrm{sort}(Q)\log_m \frac{N}{B})$ I/Os, again improving the best previously known bound."
}