# Indexed access with deletion

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 invalid mark.)
• 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:

• lookup(2): returns 2
• delete(2): now ar == ['a','b',null,'d','e']
• lookup(2): returns 3
• delete(0): now ar == [null,'b',null,'d','e']
• lookup(2): returns 4

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.

• Do you think the following can be done in $O(n)$ time? Given two permutations $\pi$ and $q$ of $[n]$, compute the vector $x$ such that, for each $t\in [n]$, $x_t$ is the number of pairs $(s, \pi_s)$ such that $s \in [t]$ and $\pi_s \le q_t$. It seems to me that if your desired data structure exists, then this could be done [think of this as, at each time $t\in [n]$, bit $\pi_s$ is toggled from 0 to 1, and then $x_t$ is the number of bits set to 1 that have index at most $q_t$], but my intuition is that this cannot be done in $O(n)$ time. Aug 2 at 20:44
• If all deletions come before lookups (one of the special cases you mention), then isn't it easy to do it in $O(n)$ time? (When the first lookup occurs, just scan the array, filtering out the deleted items, and putting the non-deleted items in order into a new array.) Aug 5 at 15:10
• @NealYoung Yes, that's what I had in mind. And I wonder how far you can push that idea. Aug 7 at 1:01

This is a subproblem of dynamic rank select, and can be done in $$O(\log n / \log w)$$, following "Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search".
• Note: the parameter $w$ in this answer is the word size, so in the standard model $w=\Theta(\log n)$, giving time $O(\log(n)/\log\log n)$. Aug 3 at 10:43