# Predecessor Queries in Dynamic Integer Sets

## Gerth Stølting Brodal

In * Proc. 14th Annual Symposium on Theoretical Aspects of Computer Science*, volume 1200 of * Lecture Notes in Computer Science*, pages 21-32. Springer Verlag, Berlin, 1997.

## 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 loglog *n*≤ *f*(*n*)≤
\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*(*n*2^{ε
w}) for an arbitrary constant ε>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*/loglog *n*) time while
having worst case *O*(loglog *n*) update time.

**Copyright notice**
© Springer-Verlag Berlin Heidelberg 1997. All rights reserved.

**Online version**

stacs97.pdf (207 Kb)

**DOI**

10.1007/BFb0023445

**Slides**
stacs97.pdf (14326 Kb)

**BIBT**_{E}X entry

@incollection{stacs97,
author = "Gerth St{\o}lting Brodal",
booktitle = "Proc. 14th Annual Symposium on Theoretical Aspects of Computer Science",
doi = "10.1007/BFb0023445",
isbn = "978-3-540-62616-9",
pages = "21-32",
publisher = "Springer {V}erlag, Berlin",
series = "Lecture Notes in Computer Science",
title = "Predecessor Queries in Dynamic Integer Sets",
volume = "1200",
year = "1997"
}