Assume I want to insert elements $1$ to $n$ into a data structure exactly once, and perform predecessor queries while inserting these elements (so insert(x) and 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 insertionsOperations = [1,3,-3,5,-1,4,-5,-4,2,-2]DS.query(Operations)//this runs in O(n) timeAssume -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.
Predecessor query where the insertion order is known
data structures;runtime analysis