Online Sorted Range Reporting
[.pdf]
Abstract
We study the following one-dimensional range reporting problem: On an
array~A of n elements, support queries that given two indices i≤ j
and an integer k report the k smallest elements in the subarray
A[i..j] in sorted order. We present a data structure in the RAM model
supporting such queries in optimal O(k) time. The structure uses O(n)
words of space and can be constructed in O(n log n) time. The data
structure can be extended to solve the online version of the problem, where
the elements in A[i..j] are reported one-by-one in sorted order, in
O(1) worst-case time per element. The problem is motivated by (and is a
generalization of) a problem with applications in search engines: On a tree
where leaves have associated rank values, report the highest ranked leaves
in a given subtree.
Finally, the problem studied generalizes the classic range minimum query (RMQ) problem on arrays.
Bibtex Entry
