Finding median from given range
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.