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

From MaRDI portal
scientific article; zbMATH DE number 6208167
  • A Simple Linear-Space Data Structure for Constant-Time Range Minimum Query
Language Label Description Also known as
English
A simple linear-space data structure for constant-time range minimum query
scientific article; zbMATH DE number 6208167
  • A Simple Linear-Space Data Structure for Constant-Time Range Minimum Query

Statements

A simple linear-space data structure for constant-time range minimum query (English)
0 references
A Simple Linear-Space Data Structure for Constant-Time Range Minimum Query (English)
0 references
0 references
0 references
2 May 2019
0 references
13 September 2013
0 references
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.
0 references
range minimum query
0 references
RMQ, data structures
0 references
constant time
0 references
linear space
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references

Identifiers

0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references