Help Privacy Policy Disclaimer
  Advanced SearchBrowse




Conference Paper

Predecessor Queries in Dynamic Integer Sets


Brodal,  Gerth Stølting
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available

Brodal, G. S. (1997). Predecessor Queries in Dynamic Integer Sets. In R. Reischuk, & M. Morvan (Eds.), Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science (STACS-97) (pp. 21-32). Berlin, Germany: Springer.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-3976-8
We consider the problem of maintaining a set of $n$ integers in the range $0..2^{w}-1$ under the operations of insertion, deletion, predecessor queries, minimum queries and maximum queries on a unit cost RAM with word size $w$ bits. Let $f(n)$ be an arbitrary nondecreasing smooth function satisfying $\log\log n\leq f(n)\leq \sqrt{\log n}$. A data structure is presented supporting insertions and deletions in worst case $O(f(n))$ time, predecessor queries in worst case $O((\log n)/f(n))$ time and minimum and maximum queries in worst case constant time. The required space is $O(n2^{\epsilon w})$ for an arbitrary constant $\epsilon>0$. The RAM operations used are addition, arbitrary left and right bit shifts and bit-wise boolean operations. The data structure is the first supporting predecessor queries in worst case $O(\log n/\log\log n)$ time while having worst case $O(\log\log n)$ update time.