Quick-select contiguous subarray

Motivated by the question from this blog post, the following data structure question seems interesting and fun to me.

• Preprocess: A list of numbers $A = a_1,...,a_n$
• Query(s,t,k): Return the $k$-th rank element of the sublist $A[s:t]$ where $A[s:t] = a_s,...,a_t$.

There are two trivial solutions:

• Space = $n^3$, Time = $1$. Construct a look-up table
• Space = $n$, Time = $O(n)$. Do nothing for preprocessing. Quick-select the $k$-th element in $A[s:t]$.

Is there some non-trivial solution?

$O(n)$ space with $O(\log k/\log \log n+\log \log n)$ query time is possible. See this paper.
When $k = \lceil (s-t)/2 \rceil$, this the range medians problem. There are solutions which are much better than the two trivial ones: you can answer the first $q$ queries in time $O(n\log q + q\log n)$. I believe the algorithms can be adapted to arbitrary rank. References: