This particular case is of special interest since finding the [[median]] has several applications.<ref name=heriel>{{cite journalbook |first1arxiv=Sariel0807.0222 |last1doi=Har10.1007/978-Peled3-540-87744-8_42 |author1chapter=Range Medians |title=Algorithms -link ESA 2008 |series=SarielLecture Notes in Computer Science |date=2008 |last1=Har-Peled |first2first1=S.Sariel |last2=Muthukrishnan |author2-linkfirst2=S. Muthukrishnan (computer scientist)|titlevolume=Range5193 Medians|journal=ESA|year=2008|pages=503–514 |isbn=978-3-540-87743-1 }}</ref> On the other hand, the median problem, a special case of the [[selection problem]], is solvable in ''O''(''n''), using the [[median of medians]] algorithm.<ref name=tarjanmedian>{{Cite journal | last1 = Blum | first1 = M. | authorlink1 = Manuel Blum| last2 = Floyd | first2 = R. W. | authorlink2 = Robert W. Floyd| last3 = Pratt | first3 = V. R. | authorlink3 = Vaughan Pratt| last4 = Rivest | first4 = R. L. | authorlink4 = Ron Rivest| last5 = Tarjan | first5 = R. E. | authorlink5 = Robert Tarjan | title = Time bounds for selection | doi = 10.1016/S0022-0000(73)80033-9 | journal = Journal of Computer and System Sciences | volume = 7 | issue = 4 | pages = 448–461 | date =August 1973 | url = http://people.csail.mit.edu/rivest/pubs/BFPRT73.pdf| doi-access = free }}</ref> However its generalization through range median queries is recent.<ref name=ethpaper /> A range median query <math>\operatorname{median}(A,i,j)</math> where ''A,i'' and ''j'' have the usual meanings returns the median element of <math>A[i,j]</math>. Equivalently, <math>\operatorname{median}(A,i,j)</math> should return the element of <math>A[i,j]</math> of rank <math>\frac{j-i}{2}</math>. Range median queries cannot be solved by following any of the previous methods discussed above including Yao's approach for semigroup operators.<ref name="morin kranakis" />
There have been studied two variants of this problem, the [[offline algorithm|offline]] version, where all the ''k'' queries of interest are given in a batch, and a version where all the pre-processing is done up front. The offline version can be solved with <math>O(n\log k + k \log n)</math> time and <math>O(n\log k)</math> space.
The following pseudocode of the [[Quickselect|quickselect algorithm]] shows how to find the element of rank {{mvar|r}} in <math>A[i,j]</math> an unsorted array of distinct elements, to find the range medians we set <math>r=\frac{j-i}{2}</math>.<ref name="ethpaper">{{cite journalbook |last1 arxiv=Beat0901.1761 |first1 last1=Gfeller |first2 first1=PeterBeat | last2=Sanders |author2-link first2=Peter Sanders| title=Automata, Languages and (computerProgramming scientist)|title chapter=Towards Optimal Range Medians |journal series=IcalpLecture Notes in Computer Science (1)|year date=2009 | volume=5555 | pages=475–486 |arxiv class=0901cs.1761DS |doi=10.1007/978-3-642-02927-1_40| isbn=978-3-642-02926-4 }}</ref>
