Data Structures for Range Median Queries

Gerth Stølting Brodal and Allan Grønlund Jørgensen

In Proc. 20th Annual International Symposium on Algorithms and Computation, volume 5878 of Lecture Notes in Computer Science, pages 822-831. Springer Verlag, Berlin, 2009.


In this paper we design data structures supporting range median queries, i.e. report the median element in a sub-range of an array. We consider static and dynamic data structures and batched queries. Our data structures support range selection queries, which are more general, and dominance queries (range rank). In the static case our data structure uses linear space and queries are supported in O(log n/loglog n) time. Our dynamic data structure uses O(nlog n/log log n) space and supports queries and updates in O((log n/loglog n)2) time.

Copyright notice

© Springer-Verlag Berlin Heidelberg 2009. All rights reserved.

Online version

isaac09median.pdf (158 Kb)




BIBTEX entry

  author = "Gerth St{\o}lting Brodal and Allan Gr{\o}nlund J{\o}rgensen",
  booktitle = "Proc. 20th Annual International Symposium on Algorithms and Computation",
  doi = "10.1007/978-3-642-10631-6_83",
  issn = "978-3-642-10630-9",
  pages = "822-831",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "Data Structures for Range Median Queries",
  volume = "5878",
  year = "2009"