Towards Optimal Range Medians
Preprint
Abstract
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 intervals. We describe a simple algorithm which uses O(n) space and needs $O(n\log k + k\log n)$ time to answer the first $k$ queries. This improves previous algorithms by a logarithmic factor and matches a lower bound for $k=O(n)$. Since the algorithm decomposes the range of element values rather than the array, it has natural generalizations to higher dimensional problems -- it reduces a range median query to a logarithmic number of range counting queries.
Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Median Filtering in Constant TimeIEEE Transactions on Image Processing, 2007
- Practical Entropy-Compressed Rank/Select Dictionary2007
- Range Mode and Range Median Queries on Lists and Trees2003
- Fractional cascading: I. A data structuring techniqueAlgorithmica, 1986
- Adding range restriction capability to dynamic data structuresJournal of the ACM, 1985
- Binary search trees of bounded balance1972