Efficient dynamic range minimum query

DOI10.1016/j.tcs.2016.07.002zbMath1356.68049OpenAlexW2237894741MaRDI QIDQ507385

Mikaël Salson, Alice Héliou, Martine Léonard, Laurent Mouchard

Publication date: 6 February 2017

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.07.002

zbMATH Keywords

longest common prefixrange minimum querycompressed bit vectordynamic structure

Mathematics Subject Classification ID

Searching and sorting (68P10) Data structures (68P05) Algorithms on strings (68W32)

Related Items

Faster online computation of the succinct longest previous factor array

Cites Work

• A simple linear-space data structure for constant-time range minimum query
• Compressed suffix trees with full functionality
• Compressed data structures: Dictionaries and data-aware measures
• Rank and select revisited and extended
• On (Dynamic) Range Minimum Queries in External Memory
• Succinct Representations of Binary Trees for Range Minimum Queries
• Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
• Optimal Succinctness for Range Minimum Queries
• Finding the maximum, merging, and sorting in a parallel computation model
• Parallelism in Comparison Problems
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• Optimal Dynamic Sequence Representations
• Path Minima Queries in Dynamic Weighted Trees
• Practical Entropy-Compressed Rank/Select Dictionary
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE