# Dynamic Data Structure for Sliding Window of varying size with Predecessor queries

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.

• This is very similar to cs.stackexchange.com/questions/55703/…, but am looking for worst-case bound of $O(1)$ on insertion. Sep 20, 2022 at 1:14
• Are you OK with amortized running time bounds for add(), instead of worst-case bounds?
– D.W.
Sep 20, 2022 at 5:18

One pragmatic approach is to use a dynamic array $$A$$. Store the integers in sorted order in this array. Augment this data structure with two additional indices: $$i_\min$$ (the index of the smallest element in the set), and $$i_\max$$ (the index of the largest element in the set, plus one).
Then, the predecessor operation can be implemented through binary search in $$A[i_\min \dots i_\max-1]$$. The min and max operations are trivial. The add operation involves potentially appending to the end of the array. Splice involves finding the index of $$x$$ in the array, then updating $$i_\min$$ to point to that index.
This gets close to your desired running times. Min and max run in $$O(1)$$ worst-case time. Predecessor runs in $$O(\log \|D\|)$$ time, worst-case. Add takes $$O(1)$$ amortized time, assuming you use standard implementations of dynamic arrays. Splice can be implemented so its running time is linear in the number of elements deleted (if you use a linear scan starting from $$i_\min$$); in fact, you can implement it in time logarithmic in the number of elements deleted (by using exponential search followed by binary search to find $$x$$). I suspect this might be good enough for practical purposes.