Efficient dynamic range minimum query

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.