Asymptotic bounds of the following operations

Question

I have a very simple question about the best possible big-O bounds for the following data structure:

It starts out empty When you add an element, it is inserted, and the index it was at is associated with it. So if it was the first item inserted, it's index would be zero:

14 12 19 <- items
 0  1  2 <- associated indices

Now if I delete 12 in this instance, the indexes for the other items are updated like so:

14 19
 0  1

Adding another element, like 10:

14 19 10
 0  1  2

If I were to delete 14, the 19 and 10 have their indices decreased by one.

In addition to adding and removing elements, you must also be able to search for a specific element and it should tell you what the index of that element is.

What is the tightest possible asymptotic bounds for these methods? Obviously I could do O(n) for removing elements and make search and add O(1). However, I was able to use a Fenwick tree to get O(log(n)) on add, search, and remove. Is it possible to do better than this?

Answer 1

If you could do all three operations faster than $O(\log n)$ time, then you would obtain a sorting algorithm whose running time is faster than $O(n \log n)$ time. That's known to be impossible for comparison-based algorithms.

So, you probably can't do better than $O(\log n)$ time for all three operations. In particular, you definitely can't do better using a comparison-based algorithm (one that only compares items but has no other knowledge about the values of items).

The reduction works as follows. First, scan through the list of $n$ numbers and insert each into your data structure. Second, scan through the list again; for each number $x$, look up its index, and then write it into an output array at that index. This does $2n$ operations on your data structure, so if your data structure can support insert and lookup in $O(\log n)$ time, the total running time will be $O(n \log n)$.

Answer 2

I contacted my professor about this question. He said he does not think it is not possible to do all three better than $O(\log n)$. For now I'll put this answer here for others, however if someone has a link to a proof, please do post it.

Edit: I am starting to think this problem cannot be reduced to sorting. I believe this is because we are dealing with a binary associative operator (addition) vs a binary non associative operator (comparison).

What I have noticed is that if you are trying to solve the problem of calculating any partial sum of an array, with the caveat that the data can also be modified, you cannot beat $O(\log n)$ for both calculating the partial sum and modifying the array. I am trying to come up with a proof for this.