# Finding median from given range

What is the most effective way of finding median from $N$ numbers within given range ? It is guaranted that $N \leq 10^{9}$.

The input consists of $L$ lines.

Each line consists either of:

a) S X , which means store number $X$, where $X \leq 10^{9}$.

or

b)F X Y, which means find median from stored numbers within range $(X,Y)$. where $1 \leq X,Y \leq 10^{9}$

For each F X Y ( median range request ) it should print the median from all stored numbers within range $(X, Y)$

Example:

Suppose the input:

S 20
S 10
S 22
S 30
S 25
F 21 30
S 5
S 7
S 9
F 5 20


Output:

   Median from range (21, 30) : 25
Median from range (5, 20) : 9


Explanation:

The first median request for range (21, 30) satisfie 3 numbers: 22 25 30 where the median is 25.

The second median request for range (5, 20) satisfie 5 numbers: 5, 7, 9, 10, 20 and we pick up the median which is 9.

The mean is not guaranted to be close to median. The requests for storing S do not have to go consecutevly.

• The input consists of N random numbers ( unsorted ) which you store. Then there go requests for median range calculation which for each request print the median within the range. There is not guarantee that mean is near median. – kvway Nov 4 '17 at 20:53
• @Evil I edited my question entirely since another numbers for storing can come after median request. So u would have to sort the array many times which would be slow. – kvway Nov 4 '17 at 21:46
• Could you credit the sources? Where have you encountered this task? – Evil Nov 4 '17 at 22:21

It can be done in $O(L \log L)$ time, which is optimal by reduction from sorting.

Consider a Red-Black Tree $T$ (or any other self-balancing tree) where each node $v$ is augmented with $s(v)$, the number of nodes in the subtree rooted in $v$. Keeping such information updated between insertions is trivial.

In order to show that such structure supports median queries in $\log L$ time, it is sufficient to show that we can perform the following operations in $\log |T|$ time:

• Given $v \in T$, determine $\#v$.

• Given $n \in \mathbb{N}$, find $v \in T$ such that $\#v = n$.

To solve the first problem, initialize a variable $x := 0$ and then find $v$. Whenever in the search you are located at a node $w$, if you move right, it means that $v$ is higher than $w$ and each node in the left child of $w$. In such a case, we set $x := x + s(w.left) + 1$. When we reach $v$, we similarly set $x := x + (v.left) + 1$.

After that last update, it will hold $x = \#v$, that is true because $v$ is the minimum of the tree $T_L$ obtained starting from $T$ and cutting the left branch every time you moved to the right while searching $v$, and, conversely, the maximum of the analogous $T_R$.

The second problem can be solved by a similar idea: initialize $x:=0$ to keep track of how many elements you "discarded" by going right, and then perform a dichotomic search.