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 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.

  • 1
    $\begingroup$ Please check my edits to make sure that they reflect your original meaning. Can you illustrate the problem by providing an example of what you're talking about? I mean, with input and output. Thanks! $\endgroup$ – Patrick87 Apr 25 '12 at 14:27
  • 2
    $\begingroup$ So, if I understand it correctly, you do the following sequence $n$ times: insert some element $x$ + delete an arbitrary number of elements + do a query for the predecessor of $x$. You want to bound the total time taken by every sequence to be $O(n)$, for a total running time of $O(n^2)$? $\endgroup$ – Alex ten Brink Apr 25 '12 at 14:38
  • $\begingroup$ actually I want to bound each operation by amortized time O(1), and the entire sequence of operation O(n). I wil update my problem with an example. $\endgroup$ – Chao Xu Apr 25 '12 at 18:33
  • 1
    $\begingroup$ Are the elements to be inserted sorted to begin with, or unsorted but have keys [1,n]? $\endgroup$ – Joe Apr 25 '12 at 18:43
  • $\begingroup$ the element to be inserted are natural numbers. The insertion order might be different from its natural order. See the example. $\endgroup$ – Chao Xu Apr 25 '12 at 19:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.