A Simple Integer Successor-Delete Data Structure

To support successor queries on a statics set, the canonical solution is to store the values in sorted order in an array and perform successor queries using binary search in $𝒪(\log |S|)$ time. In the static case of integers, the successors can be stored explicitly in an array of size $n$, and successor queries can be looked up in constant time. If the set $S$ is dynamic, the classic solution is to store the values in a balanced binary search tree, like an AVL-tree [1] or a red-black tree [12], supporting insertions, deletions, and successor and predecessor queries in $𝒪(\log |S|)$ time. Binary search trees are inherently node oriented, where each of the $|S|$ nodes stores at least a value and two pointers to its two children, and possibly some bits of balance information (splay trees [20] do not store any balance information in the nodes, but the time bounds are amortized). Implicit binary search trees [7, 8, 15] reduce the space usage to a single array of size $|S|$ storing a permutation of $S$ (all additional information is encoded in the permutation of the values). In this paper we even allow the data structures to use space $𝒪(n)$, where $n$ can be much larger than $|S|$ after many deletions. Another binary tree solution is an augmented static binary tree with leaves left-to-right representing $1,\mathrm{\dots },n$, and where each node stores the maximum non-deleted node in its subtree. Such a tree can be stored in an array of size $𝒪(n)$ (where the children of node $i$ are nodes $2i$ and $2i+1$, like in the binary heaps by Williams [28]) and supports updates and successor queries in $𝒪(\log n)$ time.

Exploiting that values are integers, van Emde Boas, Kaas and Zijlstra [25, 26] presented a dynamic data structure supporting insertions and deletions, and predecessor and successor queries in $𝒪(\log \log n)$ time and $𝒪(n)$ space. Lower bound trade-offs between query time and space usage (in the cell-probe model) were studied by Beame and Fich [3] and Pătraşcu and Thorup [16]. Succinct rank-select data structures, i.e., data structures using space ${\log }_2\left(\genfrac{}{}{0pt}{}{n}{|S|}\right)+o(n)$ bits close to the information theoretic lower bound, can also be used to answer successor queries, see, e.g., the recent dynamic rank-select structure by Li, Liang,Yu, and Zhou [14]. Note that dynamic rank-select data structures have a lower bound of $\mathrm{\Omega }(\log n/\log \log n)$ time, see Pătraşcu and Thorup [17] – a higher lower bound than for predecessor and successor queries. Pibiri and Venturini [19] presented a data structure supporting insertions and deletions in $𝒪\left(\frac{\log n}{\log \log n}\right)$ amortized time, and successor and predecessor queries in $𝒪(\log \log n)$ time, using ${\log }_2\left(\genfrac{}{}{0pt}{}{n}{|S|}\right)+O(|S|)$ bits of space. Dinklage, Fischer and Herlez [5] did a comprehensive experimental study of dynamic integer predecessor data structures supporting both insertions and deletions.

In this paper we only consider the decremental version of the problem, where values can only be deleted and never be inserted again. We allow the deletion of an already deleted value. This problem is in the literature known as the interval union-find problem: Consecutive deleted integers form intervals with their (non-deleted) successor. Deleting an integer $i$ unions the two intervals of deleted integers to the left and right of $i$. Italiano and Raman [13, Chapter 5.3] give a survey of the results for the interval union-find problem and list some applications. By exploiting the power of the RAM model, a data structure by Gabow and Tarjan [9] for the interval union-find problem supports successor queries in constant time and deletions in amortized constant time (see [22] for an introduction to amortized time analysis): Partition the integers $\{1,\mathrm{\dots },n\}$ into microsets of $b=\lceil \log n\rceil$ consecutive values. For each microset store the values in $S$ as a bitvector of length $b$ in a single word, and handle queries on a microset either by tabulation or dedicated RAM instructions (for finding the least or most significant set bit in a word¹¹1https://en.wikipedia.org/wiki/Find_first_set). A separate interval-union data structure is maintained for the macroset set $\overline{S}\subseteq \{1,\mathrm{\dots },\lceil n/b\rceil \}$, where $i\in \overline{S}$ if and only if the $i$-th microset is non-empty, i.e., $S\cap [1+(i-1)\cdot b,i\cdot b]\ne \mathrm{\varnothing }$. The macroset structure consists of an array of size $\lceil n/b\rceil$ storing pointers to the nearest non-empty successor microset structure. The pointers are updated using the “relabel the smaller half” method when a microset becomes empty. While deletions and queries to microsets and queries to the macroset take constant time, deletions to the macroset take amortized $𝒪(\log n)$ time, but only happens when all $b$ values in a microset has been deleted, i.e., the overall time for Delete becomes amortized $𝒪\left(1+(\log n)/b\right)=𝒪(1)$. The macroset data structure is in the literature known as the weighted quick-find data structure, and is attributed to McIlroy and Morris by Aho, Hopcroft and Ullman [2].

The interval union-find problem is a special case of the union-find problem, where an initial set of $n$ singleton sets are maintained under the union of two sets containing two values $i$ and $j$, $\text{Union}(i,j)$, and the query $\text{Find}(i)$ that returns a representative value for the set containing $i$. Galler and Fischer [10] introduced the rooted tree representation for the union-find problem, where each set is represented by a rooted tree, the root is the representative of the set, and each node stores a pointer to the parent node. A $\text{Find}(i)$ operation traverses the path from node $i$ to the root, and compresses the path so that all visited nodes are shortcut to have the root as their parent, and $\text{Union}(i,j)$ performs $\text{Find}(i)$ and $\text{Find}(j)$ and links the two roots, making the smaller tree (with respect to size or “rank”) a child of the root of the larger tree. Path compression and weighted linked can be combined or applied separately. Only applying linking by size gives $𝒪(\log n)$ time Union and Find operations (Fischer [6]), whereas naive linking with path compression gives amortized $𝒪(\log n)$ time Union and Find operations (Tarjan and van Leeuwen [23, Theorem 4]). Tarjan [21] showed that combining path compression with weighted linking implies $m\ge n$ Find operations take $𝒪(m\cdot \alpha (m,n))$ time, where $\alpha (m,n)$ is a very slowly growing inverse Ackermann like function. Tarjan and van Leeuwen [23] analyzed various variations of path compression for the union-find problem. They proved that path halving achieves asymptotically identical time $\mathrm{\Theta }\left(m{\log }_{1+m/n}n\right)$ as path compression, for $m\ge n$ Find operations. Path halving was introduced by van Leeuwen and van der Weide [24, 27]. Union-find structures replacing weighted linking by randomized linking were considered by Goel, Khanna, Larkin and Tarjan [11], avoiding the space usage for weights or ranks. See Italiano and Raman [13, Chapter 4.2] for a survey of the results for the union-find problem. An experimental evaluation of 55 union-find data structures was done by Patwary, Balir and Manne [18] in the context of computing the connected components of various graphs, where a variant of Rem’s union-find data structure (described by Dijkstra [4, Chapter 23]) turned out to achieve the best performance.

Any union-find structure can be combined with the microset-macroset idea to solve the interval union-find problem. For the union-find structure using linking by rank and path compression, we obtain an interval union-find structure supporting deletions and successor queries in amortized $𝒪(1)$ time: $d$ deletions cause at most $𝒪(d/\log n)$ unions in the macro-structure, creating $O(d/\log n)$ links. Since a link changing parent during a path compression is linked to a higher ranked node, a link can at most be changed $𝒪(\log n)$ times, and the total number of link updates during path compressions is $𝒪(d/\log n\cdot \log n)=𝒪(d)$. The resulting structure uses space $𝒪(n)$ bits.

The data structure we consider in Figure 3, is essentially the same as the union-find data structure by Rem, both consisting of an array of self-loops and forward pointers, except that we only consider the restricted case of the interval union-find problem, allowing us to simplify the operations. We apply path compression without weighted linking, where the representative of a set is the successor of all values in the set, and where $\text{Delete}(i)$ is $\text{Union}(i,i+1)$, that links $i$ below $i+1$ without performing $\text{Find}(i+1)$, i.e., without performing a path compression and where $i+1$ is not necessarily a root.

Heavily inspired by the results of Tarjan and van Leeuwen [23], we obtain the following results. For the successor-delete data structure in Figure 3 we obtain the following result.

Note that for a sublinear number of queries, $s\le n$, the time is $𝒪(n+d+s\cdot \log s)$, e.g., for $s=𝒪(n/\log n)$ the time is $𝒪(n+d)$. For a superlinear number of queries, where $s\ge n^{1+\epsilon }$ for a constant $\epsilon >0$, the time is $𝒪\left(n+d+s\cdot \left(1+{\log }_{n^{1+\epsilon }/n}n\right)\right)=𝒪\left(n+d+s\cdot (1+1/\epsilon )\right)$.

Our second result is that the data structure also supports the range reporting query $\text{RangeReport}(i,j)$ in Figure 4, that reports $S\cap [i,j]$ in sorted order. Provided we never delete a value already deleted or we use the $\text{Delete}(i)$ operation in Figure 4, that only modifies $A[i]$ if $i$ has not yet been deleted, we obtain the following result.

Finally, a slight modification of our data structure also supports predecessor queries, see Figure 3 in Section 4, and obtains the following result.

It should be noted that maintaining two copies of the successor-delete data structure of Theorem 2, one for each direction for reporting successor and predecessor queries, respectively, actually achieves Theorem 3. The advantage of the data structure in Section 4 is that the space usage is only a single array of $n$ integers, and deletions only need to update a single array instead of two arrays.

In Section 6 we present our experimental results of comparing our data structure to the weighted quick-find data structure and the two-pass weighted union-find data structure with path compression, with and without using microsets.

Throughout this paper we consider maintaining a set $S\subseteq \{1,2,\mathrm{\dots },n\}$. We let $\mathrm{succ}(S,i)=\min \{j\in S\mid j\ge i\}$ and $\mathrm{pred}(S,i)=\max \{j\in S\mid j\le i\}$ denote the successor and predecessor of $i$ in $S$, respectively. We assume that the values $1$ and $n$ are never deleted, such that the $\mathrm{succ}(S,i)$ and $\mathrm{pred}(S,i)$ are always defined, for $1\le i\le n$. (In our implementations we actually consider the integers $\{0,1,\mathrm{\dots },n,n+1\}$, where $0$ and $n+1$ are never deleted, such that intuitively $0$ acts as $-\mathrm{\infty }$ and $n+1$ as $+\mathrm{\infty }$.)

Consider the operations in Figure 3, and assume we perform $\text{Init}(n)$ followed by $d$ Delete and $s$ Succ operations in an arbitrary order. The Init operation together with the $d$ Delete operations clearly take $𝒪(n+d)$ time. What remains is to analyze the time spent on the $s$ Succ queries.

We assume that we never delete a value that is already deleted (or we use the Delete operation in Figure 4). We later show that this assumption is not necessary. Under this assumption, $A[i]=i$ until $i$ is deleted, where $A[i]$ is set to $i+1$. Subsequently, $A[i]$ is only changed by path compressions increasing $A[i]$, i.e., over time $A[i]$ is non-decreasing.

For a successor query $\text{Succ}(i)$, we denote the index $\mathrm{succ}(S,i)$ the root of the query. Let $R$ be the set of all root indices for the $s$ Succ queries during the sequence of operations. Clearly $|R|\le \min (s,n)$. Consider the indegree of an index $i$ over time. While $i-1$ is not deleted, the indegree of $i$ is zero. When $i-1$ is deleted, $A[i-1]$ is set to point to $i$, and $i$ gets indegree one. If $i$ is never the root of a query, $i\notin R$, $i$ will never get another in-pointer, since path compressions only change pointers to point to the root of a query, and when $A[i-1]$ is increased (because of a path compression), $i$ gets indegree zero and the indegree of $i$ remains zero for the remainder of the sequence of operations.

A $\text{Succ}(i)$ query accesses a sequence of indices in $A$, where $i_0=i$, $i_{j+1}=A[i_j]$ for , and $A[i_p]=i_p=\mathrm{succ}(S,i)$. For the query we count separately the accesses to three indices: the index $i_0$ where the query starts, and the last two indices $i_{p-1}$ and $i_p$, where the pointers do not change. For the intermediate nodes $i_1,\mathrm{\dots },i_{p-2}$, we know they have indegree at least one before the query (since they are on the query path) and the in-pointer is updated (since we use path compression). If $i_j\notin R$ ($1\le j\le p-2$), then by the above discussion $i_j$ had indegree one before the query (a pointer from $i_j-1$) and indegree zero after the query, and no further query can have $i_j$ as an intermediate index (but we could visit $i_j$ because of a $\text{Succ}(i_j)$ query, where it would play the role of “$i_0$”). It follows that the total number of accesses by all Succ queries to intermediate nodes not in $R$ is at most $n$. It follows that the total number of nodes accessed by all queries is at most $3s+n$ plus the number of accesses to intermediate nodes in $R$.

To bound the remaining number of accesses to intermediate nodes in $R$ we introduce the notion of rank (like in [23]). For $i\in R$ with , we define the rank of $i$ to be $r_i=\lfloor {\log }_{\mathrm{\Delta }}{w}_i\rfloor$, where $\mathrm{\Delta }=\max (2,\lceil s/n\rceil )$ and $w_i=\left|R\cap [i,A[i])\right|\ge 1$, i.e., the rank of $i$ is the base $\mathrm{\Delta }$ logarithm of the number of indices between $i$ and $A[i]$ in the array (excluding $A[i]$) that eventually become a root during the sequence of operations. If $i\in R$ has rank $r$, then . Ranks are upper bounded by $\lfloor {\log }_{\mathrm{\Delta }}|R|\rfloor$. We refine each rank $r$ into $\mathrm{\Delta }-1$ levels, , where an index $i$ of rank $r$ has level $\mathrm{\ell }$ if . Consider a path compression that shortcuts an index $i\in R$ over another index $j\in R$, i.e., $i\le A[i]\le j\le A[j]$ before the shortcut is made and the new value of $A[i]$ is at least the old value of $A[j]$. If then the rank of $i$ increases by at least one (to rank $\ge r_j$), but if $r_i=r_j$, then $r_i$ does not necessarily increase, but the level of index $i$ increases by at least one. It follows that for each Succ query and rank $r$ at most one accessed index of rank $r$ in $R$ does not change neither rank nor level (the rightmost rank $r$ index accessed). Over the sequence of operations, an index in $R$ can at most increase rank $\lfloor {\log }_{\mathrm{\Delta }}|R|\rfloor$ times and for each of the $1+\lfloor {\log }_{\mathrm{\Delta }}|R|\rfloor$ ranks it can increase level at most $\mathrm{\Delta }-2$ times. It follows that the total number of accesses to nodes for all Succ queries is at most

The total time for the sequence of operations becomes $𝒪\left(n+d+s+(s+|R|\mathrm{\Delta }){\log }_{\mathrm{\Delta }}|R|\right)$. Using $\mathrm{\Delta }=\max (2,\lceil s/n\rceil )$ and $|R|\le \min (s,n)$, the total time for $\text{Init}(n)$, $d$ Delete and $s$ Succ queries is $𝒪\left(n+d+s\cdot (1+{\log }_{\max (2,s/n)}\min (s,n))\right)$, as stated in Theorem 1.

To avoid the assumption that we never delete a value that is already deleted, observe that performing $\text{Delete}(i)$ when $A[i]>i$, resets $A[i]\leftarrow i+1$. If $i\in R$, then this causes $w_i$ to be reset to one, i.e., the rank of $i$ is reset to zero and the level of $i$ to one. But notice that the first path compression accessing $i$ will increase $A[i]$ to at least the value before the deletion, i.e., the lost (rank, level) potential is regained by the first access to $A[i]$. So, in the analysis above we only need to account for one additional access to $i$ for each $\text{Delete}(i)$ operation. If $i+1\notin R$, then we above used that $i+1$ would never get indegree one again, if $A[i]>i+1$, and argued that we only would visit $i$ once as an intermediate. Setting $A[i]\leftarrow i+1$ will cause $i+1$ once again to gain indegree one, allowing one additional access to $A[i]$ as an intermidate node. We charge these two additional accesses to the deletion. The remaining analysis is unchanged, and Theorem 1 holds without the assumption that we never delete a value that is already deleted.

In Figure 4 we show how to implement $\text{RangeReport}(i,j)$ using repeated calls to Succ. If $k$ is the size of the total output by $r$ RangeReport operations, these in total perform at most $r+k$ calls to Succ. We can replace $s$ in Theorem 1 with $s+r+k$ to obtain a bound on the total time for a sequence of operations also containing $r$ RangeReport queries. This bound is not linear in the output size $k$ though.

To give a better bound, we denote a subset of the links outer links. If $i_1$ and $i_2$ are two consecutive elements in $S$, i.e., $i_2=\mathrm{succ}(S,i_1+1)$, then the links on the path from $i_1+1$ to $i_2$ are the outer links. Observe, that RangeReport after the first Succ query has been performed only accesses outer links, which are shortcut, such that the outer path afterwards between $i_1$ and $i_2$ consists of a pointer directly from $i_1+1$ to $i_2$, i.e., all traversed links between $i_1$ and $i_2$ become non-outer links except for one. I.e., accessing the outer links can be charged to the output size plus the number of outer links becoming non-outer links, and the initial $\text{Succ}(i)$ query.

An outer link from $i$ is created when $i$ is deleted. Provided that we never set $A[i]\leftarrow i+1$ except for the initial deletion of $i$, a link that has become non-outer will never become outer again. It follows that we charge each Delete the creation of an outer link, and the total time becomes the bound given by Theorem 1 plus $𝒪(k)$ for the output size $k$, and replacing $s$ with $s+r$ in the bound, to cover the initial Succ query performed by each RangeReport. This gives the bound stated in Theorem 2.

The construction in Figure 3 is essentially the same as the structure in Figure 3 with respect to forward pointers for deleted indices. To maintain the linked predecessor chain, a $\text{Delete}(i)$ operation for $i\in S$ needs to perform a $\text{Succ}(i+1)$ operation to update $A[\mathrm{succ}(S,i+1)]\leftarrow A[i]$, before setting $A[i]\leftarrow i+1$. The work is $𝒪(1)$ in addition to the cost for the call to $\text{Succ}(i+1)$.

Similar to the argument for range-reporting queries in Theorem 2, the links followed by $\text{Succ}(i+1)$ are outer links, and we can apply the same accounting as in Theorem 2 that all outer links except one become non-outer links, and can be charged for the traversal. The link from $i$ to $i+1$ becomes a new outer link.

Each of the $p$ Pred and $r$ RangeReport queries essentially perform one Succ query, plus constant work and work linear in the output, respectively. The total work becomes the cost of $s+p+r$ Succ queries, plus the output size $k$, plus the cost of the Init and Delete operations. The bound stated in Theorem 3 follows from Theorem 2.