Range Medians

Sariel Har-Peled, S. Muthukrishnan

We study a generalization of the classical median finding problem to batched query case: given an array of unsorted $n$ items and $k$ (not necessarily disjoint) intervals in the ar…