Keeping changes in array indices

Question

Suppose an array arr[1..N] of integers. The array is changed in two ways:

• Values are being overwritten
• Items are considered invalid (by setting special value -1, for example)

I am looking for a data structure that gives answer to "What is the k-th valid item?" quickly.

With single invalid value, this is trivial. With many such values, it becomes a bit of a tangle.

I tried keeping an auxiliary array, which would contain 1 for invalid indices and 0 otherwise. I can keep prefix sums for this array and query them in O(log n) time. Then I know that there are sum(k) invalid items between 1 and k, so that the k-th item is actually at k + sum(k). But, between k and k + sum(k), there may be some invalid items again - and it gets ugly.

Is there a better solution to this problem, presumably in O(log n) time?

Have a nice day!

Answer 1

You can use order statistics tree (for example, based on RB or other balanced search tree) containing indexes. Both deletion and search will take O(logN) time

Answer 2

If you were to store just the valid indices (the actual indices, not the elements at those indices) in an order statistics tree (in addition to your array), that would allow getting the k-th item in O(log n) time.

An order statistics tree is basically a binary search tree (specifically a self-balancing one to get the required performance), but each node stores one additional value, which is the size of the subtree rooted at that node (i.e. the number of nodes below it).

This would similarly allow invalidation in O(log n) time with a simple BST delete operation.

Overwriting would take O(1) time - no changes to the tree are required.

---

Having both an array and the order statistics tree isn't strictly necessary - you could have the tree node contain the elements as well, but this would make overwriting take O(log n) instead of O(1).