Improved range minimum queries

Héctor Ricardo Ferrada Escobar; Gonzalo Navarro

Improved range minimum queries

Héctor Ricardo Ferrada Escobar
, Gonzalo Navarro

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

Abstract

Fischer and Heun [SICOMP 2011] proposed the first Range Minimum Query (RMQ) data structure on an array A[1,n] that uses 2n+o(n) bits and answers queries in O(1) time without accessing A. Their scheme converts the Cartesian tree of A into a general tree, which is represented using DFUDS. We show that, by using instead the BP representation, the formula becomes simpler since border conditions are eliminated. This leads to the fastest and most compact practical implementation to date.

Original language	English
Title of host publication	Unknown host publication
Publication date	2016
Publication status	Published - 2016
Externally published	Yes
MoE publication type	A4 Article in conference proceedings
Event	Data Compression Conference - Utah, United States Duration: 1 Jan 1800 → … Conference number: 26

Cite this

@inproceedings{9a3f532492644d3d80815389e865e152,

title = "Improved range minimum queries",

abstract = "Fischer and Heun [SICOMP 2011] proposed the first Range Minimum Query (RMQ) data structure on an array A[1,n] that uses 2n+o(n) bits and answers queries in O(1) time without accessing A. Their scheme converts the Cartesian tree of A into a general tree, which is represented using DFUDS. We show that, by using instead the BP representation, the formula becomes simpler since border conditions are eliminated. This leads to the fastest and most compact practical implementation to date.",

author = "\{Ferrada Escobar\}, \{H{\'e}ctor Ricardo\} and Gonzalo Navarro",

year = "2016",

language = "English",

booktitle = "Unknown host publication",

note = "Data Compression Conference ; Conference date: 01-01-1800",

}

TY - GEN

T1 - Improved range minimum queries

AU - Ferrada Escobar, Héctor Ricardo

AU - Navarro, Gonzalo

N1 - Conference code: 26

PY - 2016

Y1 - 2016

N2 - Fischer and Heun [SICOMP 2011] proposed the first Range Minimum Query (RMQ) data structure on an array A[1,n] that uses 2n+o(n) bits and answers queries in O(1) time without accessing A. Their scheme converts the Cartesian tree of A into a general tree, which is represented using DFUDS. We show that, by using instead the BP representation, the formula becomes simpler since border conditions are eliminated. This leads to the fastest and most compact practical implementation to date.

AB - Fischer and Heun [SICOMP 2011] proposed the first Range Minimum Query (RMQ) data structure on an array A[1,n] that uses 2n+o(n) bits and answers queries in O(1) time without accessing A. Their scheme converts the Cartesian tree of A into a general tree, which is represented using DFUDS. We show that, by using instead the BP representation, the formula becomes simpler since border conditions are eliminated. This leads to the fastest and most compact practical implementation to date.

M3 - Conference contribution

BT - Unknown host publication

T2 - Data Compression Conference

Y2 - 1 January 1800

ER -