$T$ as the union of subintervals
Let $U = [1,n-1]$. In your problem, you can think of $S$ as elements removed from $U$. Removing an element splits $U$ into several smaller subintervals. The union of all these subintervals generates $T$.
Let $S' = S \cup {0,n}$. Working with $S'$ instead of $S$ will make some definitions more consistent and simpler.
Now assuming that elements of $S'$ are stored in a BST $S'\tau$, then each node $y$ of the BST induces a left interval $L_y = [y_p+1,y-1]$ where $y_p$ is the predecessor of $y$ in $S'\tau$. Note that since $0 \in S'\tau$, all elements of $S$ have predecessors in $S'\tau$.
The left intervals of all $y \in S'_\tau$ are exactly the subintervals that generates $T$.
Median Finding
The algorithm that will be described here is a modification of the order statistic tree.
First note that if we write down all the elements of $T$ in sorted order, the position of the median of $T$ in $T$ is $m = \left\lceil{\frac {n - |S|} 2}\right\rceil$.
Now, for each node $y \in S'\tau$, let $size(y) = size(y{l}) + size(y_{r}) + |L_y|$, where $y_{l}$ and $y_{r}$ are the left and right children of $y$, respectively, and $|L_{y}|$ is the size of the left interval of $y$. If $y_{l}$ does not exist then $size(y_{l}) = 0$. Similarly $size(y_{r}) = 0$, if $y_{r}$ does not exists.
Essentially, $size(y)$ gives the number of elements of $T$ in $y$'s subtree.
Let rank of $y$ be the number of elements of $T$ that is less than $y$.
To find the median, we first select $x$, the minimum node in $S'$ with rank greater than or equal to $m$.
1. 743
Initialize $y$ to be the root of $S'_\tau$ and $m' = m$.
2. Let $r = size(y_l) + |L_y|$.
3. If $r \ge m'$ and $size(y_l) \lt m'$ then $x = y$ and stop.
4. Else if $r \ge m'$ and $size(y_l) \ge m'$, let $y = y_l$ and go to step 2.
5. Otherwise, let $m' = m' - r$ and $y = y_r$ and go to step 2.
Once $x$ is found the median of $T$ is equal to $x_p + (m - size(x_l))$.
Notes
The algorithm can be implemented by augmenting a BST such that each node $y$ stores $size(y)$. This value can easily be updated in $O(1)$ time per node in the path during insert and delete. When the number of elements $n$ increases, it is also trivial to find node $n$ in the BST and update its value. It is assumed that $n$ is the initial element of the BST, prior to any insert.
If the BST is balanced the running-time of the median finding algorithm is $O(\log n)$. 743