Range Minimum Queries in Minimal Space
| Autor: | Russo, Luís M. S. |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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 commands 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(\alpha(n))$ amortized time for the online version, where $\alpha(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(\ell)$ where $\ell$ is the maximum number active $i$ positions. We implemented our data structure and show that it is competitive against existing alternatives. We obtain comparable command processing time, in the nano second range, and much smaller space requirements. Comment: 29 pages, 3 figures, 3 tables, 6 algorithms |
| Databáze: | arXiv |
| Externí odkaz: |
|