Assume I want to insert elements $1$ to $n$ into a data structure exactly once, and perform predecessor queries while inserting these elements (so
pred(x) always come in pairs). The predecessor of $x$ is the largest number in the data structure that is smaller than $x$.
The data structure is created by preprocessing the list of insertions.
When I start to insert elements, an adversary decides to delete some of the elements I have inserted, by adding any number of deletion operations between my insertions.
A query input to the data structure is a sequence of insertions and deletions, which is the insertion sequence with deletions inserted. The output of the query is the result of the $n$ predecessor queries executed when the elements are inserted.
Can one design a data structure so the query takes $O(n)$?
Here is an example.
Insertions = [1,3,5,4,2] DS = makeDataStructure(Insertions)//Runs in polynomial time //add some deletions into insertions Operations = [1,3,-3,5,-1,4,-5,-4,2,-2] DS.query(Operations)//this runs in O(n) time
Assume -i = delete i. And pred(x) = 0 if there is nothing before it. result would be:
[pred(1)=0, pred(3)=1, pred(5)=1, pred(4)=0, pred(2)=0]
for example, the 3rd in the result is
pred(5)=1 instead of 3 because 3 is deleted when 5 is inserted.