<p>$O(n)$ space with $O(\log k/\log \log n+\log \log n)$ query time is possible. See <a href="http://dl.acm.org/citation.cfm?id=2133099">this paper</a>.</p>

CC BY-SA 3.0
2016-07-14T14:34:34.577Z
2016-07-14T15:09:44.963Z
2016-07-14T15:09:44.963Z
Chao Xu
<p>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: </p>

<ul>
<li><a href="http://www.cs.rutgers.edu/~muthu/medians.pdf" rel="nofollow">paper</a> that defined the problem</li>
<li><a href="http://arxiv.org/pdf/0901.1761v1.pdf" rel="nofollow">best known</a> algorithm</li>
<li>an <a href="http://sites.google.com/site/algoresearch/new.pdf" rel="nofollow">improvement</a> for $q = \Omega(n^2)$ queries</li>
</ul>

CC BY-SA 3.0
2016-08-20T15:41:06.113Z
The link for "improvement" links to "http://file///Users/anikolov/Downloads/new.pdf", which is a file on your personal computer, not on the internet.
jbapple
CC BY-SA 3.0
2016-08-20T20:57:22.773Z
@jbapple fixed now
Sasho Nikolov
CC BY-SA 3.0
2016-08-20T23:48:50.230Z
Now the link works, but it does not discuss the question.
jbapple
CC BY-SA 3.0
2016-08-21T00:39:31.080Z
@jbapple thank you! i am not sure where my mind was :) I think it should be ok now.
Sasho Nikolov
CC BY-SA 3.0
2016-07-14T14:32:23.753Z
2016-08-21T00:37:26.560Z
2016-08-21T00:37:26.560Z
Sasho Nikolov
<p>Motivated by the question from this <a href="http://11011110.livejournal.com/332617.html">blog post</a>,
the following data structure question seems interesting and fun to me.</p>

<ul>
<li>Preprocess: A list of numbers $A = a_1,...,a_n$ </li>
<li>Query(s,t,k): Return the $k$-th rank element of the sublist $A[s:t]$ where $A[s:t] = a_s,...,a_t$.</li>
</ul>

<p>There are two trivial solutions:</p>

<ul>
<li>Space = $n^3$, Time = $1$. Construct a look-up table</li>
<li>Space = $n$, Time = $O(n)$. Do nothing for preprocessing. Quick-select the $k$-th element in $A[s:t]$.</li>
</ul>

<p>Is there some non-trivial solution?</p>

<ds.data-structures><sorting>
Quick-select contiguous subarray
Thatchaphol
# Quick-select contiguous subarray

(Asked by: username_0 on 2016-07-14)

Motivated by the question from this [blog post](http://11011110.livejournal.com/332617.html),
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?

**Tags:** ds.data-structures, sorting

---

## 2 answers

### Answer by username_1 on 2016-07-14. Score: 8 | Accepted answer

$O(n)$ space with $O(\log k/\log \log n+\log \log n)$ query time is possible. See [this paper](http://dl.acm.org/citation.cfm?id=2133099).


---

### Answer by username_2 on 2016-07-14. Score: 4

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:

* [paper](http://www.cs.rutgers.edu/~muthu/medians.pdf) that defined the problem
* [best known](http://arxiv.org/pdf/0901.1761v1.pdf) algorithm
* an [improvement](http://sites.google.com/site/algoresearch/new.pdf) for $q = \Omega(n^2)$ queries

> **Comments:**
> **username_3**: The link for "improvement" links to "http://file///Users/anikolov/Downloads/new.pdf", which is a file on your personal computer, not on the internet.  
> **username_2**: @jbapple fixed now  
> **username_3**: Now the link works, but it does not discuss the question.  
> **username_2**: @jbapple thank you! i am not sure where my mind was :) I think it should be ok now.  

---

