I was wondering if anyone can point me to a data structure that supports the following operations. Goal is to create a data structure $D$ that stores 64-bit integers and provides the following operations:
- min() in $O(1)$ worst-case time
- max() in $O(1)$ worst-case time
- predecessor($x$) find the greatest element $y \in D$ such that $y \leq x $ in $O(\log \|D\|)$ worst-case time
- add($x$) in $O(1)$ worst-case time under the variant that $x \geq \max()$. When $x = \max()$, this can just be a no-op, so can effectively be ignored since max() can be done in $O(1)$ time. In other words, $D$ is essentially a set.
- splice($x$) remove from $D$ all of the elements $y$ such that $y \leq x$. This should take worst-case time proportional to the number of elements removed (i.e. amortized $O(1)$ per element removed).
I don't have explicit space constraints, but I would prefer a linear space data structure.
A doubly-linked list can provide all of these requirements except for the predecessor query in the desired time. On the other hand, tree structures can provide the predecessor query with the desired time, but don't take advantage of the fact that the data inserted is non-decreasing. So insertions and deletions fall short. A circular-array seems like a close bet, but my window does not have a fixed size, and insertions really should take $O(1)$ worst-case time.
Is this doable? If insertions were arbitrary, then this would clearly reduce to sorting... but in my case, the data inserted appears in sorted order.
I also noticed that a predecessor query can be reformulated in terms of a rank query followed by a select query, but I haven't been able to exploit existing dynamic rank-and-select data structures for this purpose.