Split find-min data structure that finds several small elements?

Question

The split find-min data structure is initialized with a sequence of elements $e_1,\ldots,e_n$, each associated with a key. The data structure supports three operations:

(1) $Split(e_i)$ that splits the sequence at position $e_i$.

(2) $FindMin(e_i)$ that returns the minimum in the interval that contains $e_i$.

(3) $DecreaseKey(e_i,k)$ that decreases the key of $e_i$ by $k$.

For instance, you may have started with $[5,2,1,4]$, where the min is $1$, then split at $2$ to get $[5][2,1,4]$, so the min of the first interval is $5$ and the min of the second interval is $1$.

Seth Pettie gave an implementation of this data structure that makes at most $O(m\log\alpha(m,n))$ comparisons when $m$ is the number of $DecreaseKey$ operations and $n$ is the number of elements ($\alpha$ is the inverse Ackermann function). For more details see the paper:

Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-Ackermann Time http://arxiv.org/abs/1407.1910

My question is: Suppose that you want to support queries not about which is the min element in each interval, but about which are the $l$ smallest elements in each interval, for a parameter $l\gg 1$ (note that you don't need to know the order among the $l$ smallest elements, only what they are). How many comparisons do you need for that?

Answer 1

Use a forest of 2-4 trees in which the keys are at the leaves. Every internal node contains a copy of the minimum key that descends from it as well as a positive integer indicating the number of values of this key descending from it.

Additionally, maintain a van Emde Boas tree containing as keys each positive integer $i$ where $e_i$ is the left-most element in one of the 2-4 trees. In the vEB tree, each integer $i$ has satellite data: a pointer to the root of the tree the key associated with $e_i$ is in.

1. $Split$ is the normal split on 2-4 trees, updating the internal node data as it proceeds. This takes logarithmic time in the size of the tree being split, while updating the vEB tree takes time corresponding to the logarithm of the logarithm of the number of trees in the forest.

2. $FindMin$, which now returns the $l$ smallest keys, does a breadth-first search down the tree containing the element in question. Starting from the root, this takes time linear in $l$. To find the root from the element, access the vEB tree, find the predecessor, then follow the pointer to that root.

3. $DecreaseKey$ modifies a single 2-4 tree, taking time logarithmic in the size of that tree.

Each $Split$ uses $O(\log \log n)$ time for the vEB operation and $O(\log n)$ key comparisons. Each $FindMin$ uses $O(\log \log n)$ time for the vEB operation and $O(l)$ key comparisons. Each $DecreaseKey$ uses $O(\log n)$ key comparisons.