A simple linear-space data structure for constant-time range minimum query (Q1740692)

The authors of this article propose a new data structure used to solve the range minimum query (RMQ) problem in \(O(1)\) time using \(O(n)\) words of space. In order to prove the efficiency of the proposed RMQ data structure, the authors compare the structure with four other RMQ data structures with the same space and time complexity \(\langle O(n), O(1)\rangle\) [\textit{J. Fischer} and \textit{V. Heun}, Lect. Notes Comput. Sci. 4614, 459--470 (2007; Zbl 1176.68058); \textit{M. A. Bender} and \textit{M. Farach-Colton}, Lect. Notes Comput. Sci. 1776, 88--94 (2000; Zbl 0959.68133); \textit{K. Sadakane}, J. Discrete Algorithms 5, No. 1, 12--22 (2007; Zbl 1137.68360); \textit{E. Ohlebusch} and \textit{S. Gog}, Lect. Notes Comput. Sci. 5721, 51--62 (2009; Zbl 1470.68040)]. The result of the comparison indicates that the proposed data structure gives the best query time, similar to the Fischer and Heun data structure. In terms of memory space, the Ohlebusch and Sadakane data structure gives the best results.