Asymptotic bounds of the following operations 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 &lt;- items
 0  1  2 &lt;- 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?
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)$.