Sorted Range Reporting
share
In sorted range selection problem, the aim is to preprocess a given array A[1: n] so as to answers queries of type: given two indices i,j (1 ≤ i≤ j ≤ n) and an integer k, report k smallest elements in sorted order present in the sub-array A[i: j] Brodal et.al.[2] have shown that the problem can be solved in O(k) time after O(n log n) preprocessing in linear space. In this paper we discuss another tradeoff. We reduce preprocessing time to O(n), but query time is O(k log k), again using linear space. Our method is very simple.
READ FULL TEXT