2009/01/13 by Beat Gfeller, Peter Sanders, Gfeller, Beat +1
Computer Science · #Advanced Data Compression Techniques #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Video Surveillance and Tracking Methods #cs.DS
paper · pdf · doi:10.48550/arxiv.0901.1761
arxiv created 2009/01/13 · openalex publication_date 2009/01/13 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(nlog k + klog 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.