Towards Optimal Range Medians

Beat Gfeller, Peter Sanders

We consider the following problem: given an unsorted array of $n$ elements, and a sequence of intervals in the array, compute the median in each of the subarrays defined by the int…