  Given an array A[1: n] of n elements drawn from an ordered set, the sorted
range selection problem is to build a data structure that can be used to answer
the following type of queries efficiently: Given a pair of indices i, j $ (1\le
i\le j \le n)$, and a positive integer k, report the k smallest elements from
the sub-array A[i: j] in order. Brodal et al. (Brodal, G.S., Fagerberg, R.,
Greve, M., and L{\'o}pez-Ortiz, A., Online sorted range reporting. Algorithms
and Computation (2009) pp. 173--182) introduced the problem and gave an optimal
solution. After O(n log n) time for preprocessing, the query time is O(k). The
space used is O(n).
  In this paper, we propose the only other possible optimal trade-off for the
problem. We present a linear space solution to the problem that takes O(k log
k) time to answer a range selection query. The preprocessing time is O(n).
Moreover, the proposed algorithm reports the output elements one by one in
non-decreasing order. Our solution is simple and practical.
  We also describe an extremely simple method for range minima queries (most of
whose parts are known) which takes al most (but not exactly) linear time. We
believe that this method may be, in practice, faster and easier to implement in
most cases.
