A Simple Linear-Space Data Structure for Constant-Time Range Minimum Query
classification
💻 cs.DS
keywords
dataqueryminimumrangesimplespacestructuretime
read the original abstract
We revisit the range minimum query problem and present a new O(n)-space data structure that supports queries in O(1) time. Although previous data structures exist whose asymptotic bounds match ours, our goal is to introduce a new solution that is simple, intuitive, and practical without increasing costs for query time or space.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.