Range majority in constant time and linear space

DOI10.1016/j.ic.2012.10.011zbMath1266.68097OpenAlexW2156839950MaRDI QIDQ1951579

Meng He, J. Ian Munro, Patrick K. Nicholson, Stephane Durocher, Matthew Skala

Publication date: 6 June 2013

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2012.10.011

zbMATH Keywords

linear space data structurerange majority queries in constant time

Mathematics Subject Classification ID

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

Related Items

Optimal encodings for range majority queries ⋮ Dynamic range majority data structures ⋮ Compressed dynamic range majority and minority data structures ⋮ Linear-space data structures for range mode query in arrays ⋮ Range majorities and minorities in arrays ⋮ Array Range Queries ⋮ Linear-space data structures for range frequency queries on arrays and trees