<p>This is a subproblem of dynamic rank select, and can be done in <span class="math-container">$O(\log n / \log w)$</span>, following <a href="https://arxiv.org/pdf/1408.3045.pdf" rel="nofollow noreferrer">&quot;Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search&quot;</a>.</p>

CC BY-SA 4.0
2022-08-03T10:43:19.177Z
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)$.
Neal Young
CC BY-SA 4.0
2022-08-07T01:24:54.910Z
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.
Matthias
CC BY-SA 4.0
2022-08-03T03:12:38.997Z
2022-08-03T03:12:38.997Z
jbapple
<p>As part of a larger data structure that I am working on, I have the following sub-problem:</p>
<p>I start with <span class="math-container">$n$</span> slots in an array.  Initially all slots are valid.  I want to support two operations:</p>
<ul>
<li><code>delete(i)</code>: delete the <span class="math-container">$i$</span>-th slot in the array (by replacing its content with an <code>invalid</code> mark.)</li>
<li><code>lookup(o)</code>: return the index of the slot that holds the <span class="math-container">$o$</span>-th still valid entry.</li>
</ul>
<p>As an example, let's start with <code>ar := ['a','b','c','d','e']</code> and show the results of a few operations:</p>
<ul>
<li><code>lookup(2)</code>: returns <code>2</code></li>
<li><code>delete(2)</code>: now <code>ar == ['a','b',null,'d','e']</code></li>
<li><code>lookup(2)</code>: returns <code>3</code></li>
<li><code>delete(0)</code>: now <code>ar == [null,'b',null,'d','e']</code></li>
<li><code>lookup(2)</code>: returns <code>4</code></li>
</ul>
<p>The solution doesn't actually have to keep the array around.  All I care about here is that lookup gives the right index.</p>
<p>I know that I can solve the problem with <span class="math-container">$O(log n)$</span> worst-case runtime per operation.  I am interested in whether it is possible to find a solution with <span class="math-container">$O(1)$</span> amortised, expected runtime per operation.  ('Expected' as in expected value averaged over random choices your algorithm might make, but for worst case input.)</p>
<p>Of course, randomisation and amortisation aren't a must.  I'd be even happier with a deterministic and worst-case bound.</p>
<p>Please either give a solution or an argument why a solution is not possible.</p>
<p>(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 <span class="math-container">$O(n log n)$</span> bound for comparison based sorting isn't possible.  We are explicitly dealing with small natural numbers only here.)</p>
<p>In addition, I'm interested in any solution that's faster than <span class="math-container">$O(log n)$</span> 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.</p>
<p>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.</p>
<p>I am also interested in any pointers you have to relevant literature.</p>

CC BY-SA 4.0
2022-08-02T20:44:34.560Z
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.
Neal Young
CC BY-SA 4.0
2022-08-05T15:10:20.630Z
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.)
Neal Young
CC BY-SA 4.0
2022-08-07T01:01:22.327Z
@NealYoung Yes, that's what I had in mind. And I wonder how far you can push that idea.
Matthias
<ds.data-structures><randomized-algorithms><amortized-analysis>
Indexed access with deletion
Matthias
# Indexed access with deletion

(Asked by: username_0 on 2022-08-02)

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.

**Tags:** ds.data-structures, randomized-algorithms, amortized-analysis
> **Comments:**
> **username_1**: 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.  
> **username_1**: 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.)  
> **username_0**: @NealYoung Yes, that's what I had in mind. And I wonder how far you can push that idea.  

---

## 1 answers

### Answer by username_2 on 2022-08-03. Score: 3

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"](https://arxiv.org/pdf/1408.3045.pdf).

> **Comments:**
> **username_1**: 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)$.  
> **username_0**: 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.  

---

