Range minimum queries in minimal space

We consider the problem of computing a sequence of range minimum queries. We assume a sequence of commands that contains values and queries. Our goal is to quickly determine the minimum value that exists between the current position and a previous position i. Range minimum queries are used as a sub-routine of several algorithms, namely related to string processing. We propose a data structure that can process these command sequences. We obtain efficient results for several variations of the problem, in particular we obtain O ( 1 ) time per command for the offline version and O ( α ( n ) ) amortized time for the online version, where α ( n ) is the inverse Ackermann function and n the number of values in the sequence. This data structure also has very small space requirements, namely O ( ℓ ) where ℓ is the maximum number of active i positions. We implemented our data structure and show that it is competitive against existing alternatives. We obtain comparable processing time, in the nanosecond range, and much smaller space requirements.

Authors

• Luís M.S. Russo

Keywords

• Range minimum queries
• Union-Find
• Disjoint sets
• Bulk queries
• String processing