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.