# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Predecessor Queries in Dynamic Integer Sets

##### 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

##### Citation

Brodal, G. S. (1997). Predecessor Queries in Dynamic Integer Sets. In R. Reischuk,
& M. Morvan (*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

##### Abstract

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.