# Efficient data structure for insertion, deletion and smallest-not-in-range query on an array of integers

I'm trying to make a data structure $$A$$ that has the following features:

• insert($$a$$) operation : insert given integer $$a$$ to $$A$$. It is assured that all integers are unique.
• delete($$b$$) operation : delete $$b$$ from $$A$$.
• smallestNotInRange($$p$$,$$q$$) : returns the smallest value $$k$$ such that $$k\in [p,q]$$ and $$k \notin A$$.
• Each operation should take $$O(\log{n})$$ time and should use $$O(n)$$ space. $$n$$ is the number of integers in $$A$$.

Because of the last function the first thing I thought of was using segment trees. However, it was not the right choice because it uses $$O(n \log n)$$ space.
The next thing I thought of was using a balanced binary search tree. Everything is good for insert and delete operations because insertion and deletion of a balanced binary search tree take worst-case runtime of $$O(\log n)$$ and the data structure use $$O(n)$$ space. The problem is with the smallestNotInRange operation. When the number of integers in range $$[p,q]$$ is less than $$\log n$$ the operation will take $$O(\log n)$$, however, when the number of integers in range $$[p,q]$$ is greater than $$\log n$$ the operation will take $$O(n)$$. How can I resolve this problem and get this to work at worst-case runtime of $$O(\log n)$$?

• What is the context where you encountered this task? Can you credit the source where you saw this or the motivation?
– D.W.
Apr 11 at 8:42

You can use a balanced BST. For each node $$n$$, let $$n.lsize$$ be the size of the left subtree of $$n$$. Insert and delete is just standard BST add and remove with size updating. To implement smallestNotInRange do the following:

1. Find node $$n_p$$ containing $$p$$. If it does not exist, then $$k =p$$, else let $$size_{p_{left}} = n_p.lsize$$.

2. Starting from the root, find the shallowest node $$n_m$$ such that $$p \le m \le q$$. To do this, check the value of the current node. If the value is less than $$p$$ move down to its right subtree. Else, if the value is greater than $$q$$ move down to its left subtree. Otherwise, the current node is $$n_m$$. If at some point, the visited subtree is empty, then $$k = p + 1$$.

3. If $$n_m.lsize - size_{p_{left}} \lt m - p$$ and $$n_m$$ is the parent of $$n_p$$, then $$k = p + 1$$. Otherwise, let $$q = m - 1$$ and repeat step 2, but this time starting at the left child of $$n_m$$, instead of the root.

4. If $$n_m.lsize - size_{p_{left}} = m - p$$ and $$m = q$$ then there is no such $$k$$. Otherwise, set $$size_{p_{left}} = -1$$, $$n_p = n_m$$, and $$p = m$$ and repeat step 2, but this time starting at the right child of $$n_m$$, instead of the root.

For step 1, it is self-explanatory why $$k=p$$ when $$n_p$$ does not exist. The variable $$size_{p_{left}}$$ is initially set to the number of elements in the left subtree of $$n_p$$, which are elements not in $$[p,q]$$.

The idea behind steps 2 to 4 is like doing a binary search to find the subrange in $$[p,q]$$ closest to $$p$$, that contains an element not in $$A$$. Step 2 is like the "finding the middle" part of the binary search.

Step 3 checks if there is a missing element in the subrange $$[p,m]$$. If there is, it continues the search in that subrange. There is a missing element when $$m-p$$, the expected number of elements in the range, is greater than $$n_m.lsize - size_{p_{left}}$$. The subtraction ensures that when $$n_p$$ is in the left subtree of $$n_m$$, we do not count the elements in the left subtree of $$n_p$$ since they are not in $$[p,m]$$.

If there is no missing element in $$[p,m]$$, step 4 performs the search in the subrange $$[m,q]$$ instead. When going to this subrange, the new $$n_p$$ will never appear as subtree of the $$n_m$$ hence, the left subtree of $$n_m$$ will also not contain elements that are not in $$[p, m]$$. Therefore, we set $$size_{p_{left}} = -1$$. This will effectively add 1 to $$n_m.lsize$$ when comparing it to $$m - p$$, since $$m-p$$ takes into account $$p$$ but $$n_m.lsize$$ doesn't.

As for the running-time, step one takes $$O(\log n)$$ in the worst-case if it happens that $$n_p$$ is a leaf of a balanced BST. For steps 2-4, this is just modified BST search. Choosing the node to visit is controlled by the result of comparing $$n_m.lsize - size_{p_{left}}$$ and $$m - p$$. Each time a node is visited, only constant amount of work is done, thus the running-time for the entire steps 2-4 is also $$O(\log n)$$ because the tree is balanced. Therefore, the entire procedure is $$O(\log n)$$.

• Thank you for your answer! I have two question. 1. On step 4, when assigning $p=m$ is $m$ the the first middle node found in step 2 or is it the one that is last node to be found in step 3? Also, how can $m=q$ when we are going left from a middle value between $p$ and $q$? 2. Can you give me some explanation runtime of the algorithm? I'm have some trouble proving the runtime of this algorithm.
– user149684
Apr 10 at 5:59
• Your question actually opened some problems with the procedure I presented, which I hope I was able to fix completely. I also changed the way the steps 3 and 4 are presented to hopefully mirror the way binary search selects the subrange that will be considered for further search. Then I added some further discussions. Feel free to ask clarifications if my changes are not enough. Apr 10 at 7:06
• Thank you for improving your answer! Shouldn't $size_{pleft}=1$ on step 4? For example, $9-5=4$ and the numbers between 9 and 5 are three numbers 6,7 and 8 so the algorithm should take step 4 again. Also, one question on runtime. If my understanding is correct, the algorithm will always do step 2 and do step 4 when there is no answer in the left branch and the algorithm will only take a left turn when the answer is in the left branch. So, is the maximum number of visits $\log n$?
– user149684
Apr 10 at 7:55
• I think you're right with setting $size_{p_{left}}$ to 1 in step 4 since at this point $n_p$ will also not be counted under the left subtree of $n_m$. As for the running-time, yes the number of visit is $O(\log n)$. Apr 10 at 8:02
• Actually I think $size_{p_{left}}$ should be -1. Check my update. Apr 10 at 8:23