# 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?

## 2 Answers

$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:

• The link for "improvement" links to "file///Users/anikolov/Downloads/new.pdf", which is a file on your personal computer, not on the internet. – jbapple Aug 20 '16 at 15:41
• @jbapple fixed now – Sasho Nikolov Aug 20 '16 at 20:57
• Now the link works, but it does not discuss the question. – jbapple Aug 20 '16 at 23:48
• @jbapple thank you! i am not sure where my mind was :) I think it should be ok now. – Sasho Nikolov Aug 21 '16 at 0:39