Efficient dynamic range minimum query

DOI10.1016/J.TCS.2016.07.002MaRDI QIDQ507385zbMATH OpenOpenAlexFDO

Authors Alice Héliou, M. Léonard, L. Mouchard, M. Salson

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

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

Recommendations

• Improved range minimum queries
• Space-efficient preprocessing schemes for range minimum queries on static arrays
• Optimal succinctness for range minimum queries
• Two-Dimensional Range Minimum Queries
• On (dynamic) range minimum queries in external memory

Cites work

• Compressed data structures: Dictionaries and data-aware measures
• Compressed suffix trees with full functionality
• Finding the maximum, merging, and sorting in a parallel computation model
• On (dynamic) range minimum queries in external memory
• Optimal succinctness for range minimum queries
• Parallelism in Comparison Problems
• Path minima queries in dynamic weighted trees
• Practical entropy-compressed rank/select dictionary
• Rank and select revisited and extended
• Space-efficient preprocessing schemes for range minimum queries on static arrays
• Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees, Prefix Sums and Multisets
• Succinct representations of binary trees for range minimum queries
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE

Cited in

(8)

• Faster online computation of the succinct longest previous factor array
• On (dynamic) range minimum queries in external memory
• Improved algorithms for the range next value problem and applications
• Processing an offline insertion-query sequence with applications
• Online sorted range reporting
• Space-efficient preprocessing schemes for range minimum queries on static arrays
• I/O-efficient range minima queries
• Improved range minimum queries

This page was built for publication: Efficient dynamic range minimum query

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q507385)