k-th smallest element in sliding segment

Question

Consider an array $a[1\ldots n]$ and another array $l = a[0]$ (initial value). At each turn we may add next element to array $l$, or remove first element from array $l$. F.e. after first iteration it could be empty or could become $a[0, 1]$. We want to find k-th smallest element at each iteration in array $l$.

First of all if size of $l$ is less than $k$ the answer is 'No'. Let's consider more interesting case.

I've decided to have two heaps (one min and one max heap).

Max heap contains all k-th smallest elements from $a[l..r]$ and min heap contains elements which are greater than the k-th smallest element. Then answer is head of max-heap (we can take it in O(1)).

But there is a small problem. What if need to consider $a[l+1 .. r]$ (so we need to push left bound). Now of course if $r - l < k$ the answer is 'No', but what should we do otherwise? I thought we should do following: if $a[l] > maxheap[0]$ then the answer doesn't change (because we will delete element greater than k-th smallest element), but what should we do with our heaps? Unfortunately I can't delete in heap by position (it takes a long time). The best we can do is delete root node in O(log n). How should I affect them?

Answer 1

Maintain an AVL tree $B$ that stores the elements in $l$. In addition, for each element $a$ in $l$, keep a pointer $p_a$ to the corresponding node in $B$.

• When an element $x$ is added to $l$, then simply insert a new node $v$ representing $x$ into $B$ and make $p_x$ point to $v$.

• When the first element $y$ of $l$ needs to be removed, delete (the node pointed by) $p_y$ from $B$.

• To report the $k$-minimum element in $l$, simply look for the minimum element in $B$ (i.e., the one stored in the leftmost node). This can be done in $O(\log n)$ time by just keeping, in each node $v$, the size of the subtree of $B$ rooted in $v$.

By combining the above operations, each turn of your problem will require $O(\log(1 + |l|)) = O(\log n)$ time.