6
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
8
$\begingroup$

$O(n)$ space with $O(\log k/\log \log n+\log \log n)$ query time is possible. See this paper.

Improve this answer
$\endgroup$
4
$\begingroup$

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:

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.