Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search
Mihai Pǎtraşcu, Mikkel Thorup · 2014
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 ≥ log n 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}. 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'89]. 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 [FOCSf83]. Ajtai et al. presented such a data structure in Yaofs 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 [STOCf90] 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.