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 tableSpace = $n$, Time = $O(n)$. Do nothing for preprocessing. Quick-select the $k$-th element in $A[s:t]$.Is there some non-trivial solution?
Quick-select contiguous subarray
ds.data structures;sorting
$O(n)$ space with $O(\log k/\log \log n+\log \log n)$ query time is possible. See this paper.