Item

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.