As part of a larger data structure that I am working on, I have the following sub-problem:
I start with $n$ slots in an array. Initially all slots are valid. I want to support two operations:
delete(i): delete the $i$-th slot in the array (by replacing its content with an
lookup(o): return the index of the slot that holds the $o$-th still valid entry.
As an example, let's start with
ar := ['a','b','c','d','e'] and show the results of a few operations:
ar == ['a','b',null,'d','e']
ar == [null,'b',null,'d','e']
The solution doesn't actually have to keep the array around. All I care about here is that lookup gives the right index.
I know that I can solve the problem with $O(log n)$ worst-case runtime per operation. I am interested in whether it is possible to find a solution with $O(1)$ amortised, expected runtime per operation. ('Expected' as in expected value averaged over random choices your algorithm might make, but for worst case input.)
Of course, randomisation and amortisation aren't a must. I'd be even happier with a deterministic and worst-case bound.
Please either give a solution or an argument why a solution is not possible.
(I suspect a solution is possible, more or less because we can do bucket sort in linear time. So a reduction of the problem to the $O(n log n)$ bound for comparison based sorting isn't possible. We are explicitly dealing with small natural numbers only here.)
In addition, I'm interested in any solution that's faster than $O(log n)$ per operation. Constant time is just what I am aiming for. I would also be interested in a solution in important special cases, eg like all deletions coming before all lookups, or the sequence of operations being known up-front instead of an online solution.
Another detail: all runtimes are for something like the word RAM model. Or more practically: I am interested in something that I can implement to run fast on real computers.
I am also interested in any pointers you have to relevant literature.