Catalog Home Page

Efficient dynamic range minimum query

Heliou, A., Léonard, M., Mouchard, L. and Salson, M. (2016) Efficient dynamic range minimum query. Theoretical Computer Science, 656 (B). pp. 108-117.

Link to Published Version:
*Subscription may be required
Free to read:
*No subscription required


The Range Minimum Query problem consists in answering efficiently the simple question: “what is the minimal element between two specified indices of a given array?”. In this paper we present a novel structure that offers a trade-off between time and space. Moreover we show how the structure can be easily maintained whenever an insertion, modification or deletion modifies the input sequence.

Item Type: Journal Article
Murdoch Affiliation: School of Engineering and Information Technology
Publisher: Elsevier BV
Copyright: © 2016 Elsevier B.V.
Item Control Page Item Control Page