Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search

We present a data structure representing a dynamic set S of w-bit integers on a w-bit word RAM. With S = n and w ≥ logn and space O(n), we support the following standard operations in O(log n/ log w) time: . insert(x) sets S = S ∪ {x}. .delete(x) sets S = S {x}. . predecessor(x) returns max{y ∈ S y <; x}. . successor(x) returns min{y ∈ S y ≥ x}. . rank(x) returns # {y ∈ S y <; x}. . select(i) returns y ∈ S with rank(y) = i, if any. Our O (log n/ log w) bound is optimal for dynamic rank and select, matching a lower bound of Fredman and Saks [STOC´99]. When the word length is large, our time bound is also optimal for dynamic predecessor, matching a static lower bound of Beame and Fich [STOC´ 99] whenever log n/ log w = O (log w/ log log w). Technically, the most interesting aspect of our data structure is that it supports all the above operations in constant time for sets of size n = w^O(1). This resolves a main open problem of Ajtai, Komlos, and Fredman [FOCS´83]. Ajtai et al. presented such a data structure in Yao´s abstract cell-probe model with w-bit cells/words, but pointed out that the functions used could not be implemented. As a partial solution to the problem, Fredman and Willard [STOC´90] introduced a fusion node that could handle queries in constant time, but used polynomial time on the updates. We call our small set data structure a dynamic fusion node as it does both queries and updates in constant time.