Sorted Range Reporting

In this paper, we investigate the following 1-d range reporting problem: preprocess an array A[1: n] of n elements so that, given a pair of indices i, j (1 <= i <= j <= n) and an integer k as query parameters, the k smallest elements of the sub-array A[i: j] can be reported efficiently. Brodal et al. [3] have shown that the problem can be solved in O(k) time after O(n log n) preprocessing in linear space. In this work, we obtain the only other possible trade-off. We reduce preprocessing time to O(n), but query time is O(k log k), again using linear space. Our method is very simple. Moreover, our algorithm reports or outputs the required elements in non-decreasing order one by one.