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?