A Simple Linear-Space Data Structure for Constant-Time Range Minimum\n Query

2011/09/20 by Stéphane Durocher, Durocher, Stephane
Computer Science · #Advanced Data Storage Technologies #Algorithms and Data Compression #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Theory and Algorithms

paper · pdf · doi:10.48550/arxiv.1109.4460

openalex publication_date 2011/09/20 · openalex created_date 2022/10/06 · openalex updated_date 2026/07/28

Abstract

We revisit the range minimum query problem and present a new O(n)-space data\nstructure that supports queries in O(1) time. Although previous data structures\nexist whose asymptotic bounds match ours, our goal is to introduce a new\nsolution that is simple, intuitive, and practical without increasing costs for\nquery time or space.\n

Related

• Range Minimum Queries in Minimal Space
• Lower Bound for Succinct Range Minimum Query
• Faster range minimum queries
• New Data Structures for Orthogonal Range Reporting and Range Minima Queries
• Space-efficient Data Structure for Next/Previous Larger/Smaller Value Queries