1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – Neal Young
    Aug 2, 2022 at 20:44
  • 1
    $\begingroup$ 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.) $\endgroup$
    – Neal Young
    Aug 5, 2022 at 15:10
  • $\begingroup$ @NealYoung Yes, that's what I had in mind. And I wonder how far you can push that idea. $\endgroup$
    – Matthias
    Aug 7, 2022 at 1:01

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ 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)$. $\endgroup$
    – Neal Young
    Aug 3, 2022 at 10:43
  • $\begingroup$ Thanks for the link to the paper. That's a good upper bound for what I am looking for. I hope that since I am interested in a sub problem and in amortised runtime, we can do better. $\endgroup$
    – Matthias
    Aug 7, 2022 at 1:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.