A simple linear-space data structure for constant-time range minimum query

DOI10.1016/j.tcs.2018.10.019zbMath1473.68059arXiv1109.4460OpenAlexW2904368314WikidataQ129023513 ScholiaQ129023513MaRDI QIDQ1740692

Stephane Durocher, Robby Singh

Publication date: 2 May 2019

Published in: Theoretical Computer Science, Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1109.4460

zbMATH Keywords

linear spacerange minimum queryconstant timeRMQ, data structures

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05)

Related Items

Encodings of Range Maximum-Sum Segment Queries and Applications, Linear-time superbubble identification algorithm for genome assembly, Efficient semi-external depth-first search, Linear-space data structures for range minority query in arrays, A simple linear-space data structure for constant-time range minimum query, Efficient dynamic range minimum query, Linear-space data structures for range mode query in arrays, Array Range Queries, Linear-space data structures for range frequency queries on arrays and trees

Uses Software

• SDSL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On space efficient two dimensional range minimum data structures
• Nearest common ancestors: a survey and a new algorithm for a distributed environment
• Encoding 2D range maximum queries
• Succinct data structures for flexible text retrieval systems
• Preserving order in a forest in less than logarithmic time and linear space
• A simple linear-space data structure for constant-time range minimum query
• Array Range Queries
• Succinct Representations of Binary Trees for Range Minimum Queries
• Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
• Fast Algorithms for Finding Nearest Common Ancestors
• A Compressed Enhanced Suffix Array Supporting Fast String Matching
• Two-Dimensional Range Minimum Queries
• Optimal Succinctness for Range Minimum Queries
• A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
• On Cartesian Trees and Range Minimum Queries
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Recursive Star-Tree Parallel Data Structure
• Path Minima Queries in Dynamic Weighted Trees
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
• STACS 2005
• Lowest common ancestors in trees and directed acyclic graphs