Vi studerar en generalisering av den klassiska median hitta problem till batched fråga fall: med tanke på en rad osorterade n objekt och k (inte nödvändigtvis separera) intervaller i matrisen, målet är att bestämma medianen i var och en av intervallen i matrisen. Vi ger en algoritm som använder O(n log n + k log k log n) jämförelser och visar en lägre gräns för  och (n log k) jämförelser för detta problem. Detta är optimalt för k = O (n/ log n).
Författarna till REF ger en lösning av RMP som kräver O(n log k+ k log n log k) tid och O(n log k) utrymme.
Range Medians
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}