Union-Find with link-by-rank to represent a binary field with simple operations

Question

I have a field $X$ of given length $n$ which is filled with zeroes in the beginning.

I only need these 3 simple operations:

GET_VALUE$(i)$: returns the value of $i$-th cell ($X[i]$)

SET_TO_1$(i)$:basically $X[i] \leftarrow 1$ for $i < n - 1$, otherwise nothing (the last cell of $X$ is always zero ($X[n-1] = 0$))

FIND$(i)$: find the least index $j \geq i$ s.t. $X[j] = 0$ (note that this operation will always succeed since the last cell is always zero)

I need the time complexity of operation GET_VALUE to be constant. And both SET_TO_1 and FIND to be in $O(\log n)$.

My thinking so far:

I am almost sure the perfect data structure for this would be Union-Find, because sets elegantly represent all such $i$ that for which FIND returns the same value. The root of the sets would be the index that is returned by the FIND operation - the only index $i$ in the set s.t. $X[i] = 0$.

The implementation of GET_VALUE operation would be also pretty straightforward. If $i$ is a root (points to itself) return $0$ and $1$ otherwise.

However this doesn't work nicely for the SET_TO_1 operation. I would want it in case it sets a cell $X[i]$ from $0$ to $1$ to join the set represented by the root $i$ to the next one (which contains the element of index $i+1$). But if I want GET_VALUE to be in $O(\log n)$ I need to use link by rank and thus I cannot choose which root of the two unified trees is preserved - but in order for this to work it must be the second one (from the $i+1$ set).

How can I fix this?

Answer 1

In each node store an additional field named "value". The value of a root $r$ represents $\text{FIND}(r)$ (so the root itself is not necessarily $\text{FIND}(r)$). For $\text{SET_TO_1}(i)$, let $r$ be the root of the tree $i+1$ belongs to, we in addition change the value of the new root to the value of $r$. Now which root becomes the new root does not matter at all.

Answer 2

This is an alternative implementation that does not use union-find. When compared to your implementation (with the tweak by xskxzr), my implementation has both advantages and disadvantages.

Advantages:

• It has a real $O(1)$ GET_VALUE instead of an amortized nearly-$O(1)$ one

• It could implement SET_TO_0, or even SET_TO(i, n) for any n (with FIND still returning the first non-zero value)

Disadvantages:

• Uses more memory

• Has a $O(\log n)$ FIND where yours is amortized nearly-$O(1)$

---

First, notice that you have one "set" operation (SET_TO_1) and two "get" operations (GET_VALUE and FIND). So you can have two structures that can handle SET_TO_1: one per get operation.

For SET_TO_1 and FIND, a balanced binary search tree that contains the elements whose value is 0 (or 1 if you want to think a bit more and not have an $O(n)$ initialization) give SET_TO_1 and FIND in $O(\log n)$.

So now we only need to handle SET_TO_1 and GET_VALUE. For which an array clearly works.

In conclusion, your structure is a balanced binary search tree T and an array A. The tree is initialized as containing all the elements, and the array as filled with zeroes.

• SET_TO_1(i) does T.remove(i) and A[i] := 1
• GET(i) returns A[i]
• FIND(i) returns T.myfind(i) (where myfind find the smallest element j in the tree such that i <= j)

myfind could be implemented as follow:

function myfind(tree, index) {
  var node = tree;
  while (not isLeaf(node)) {
    if (index == node.value) {
      return index;
    } else if (index < node.value) {
      if (node.left != null) {
        node = node.left;
      }
    } else /* if (index > node.value) */ {
      if (node.right != null) {
        node = node.right;
      }
    }
  }
  // We now are at a leaf such that there is no value of the tree between index and node.value
  // Because of this, if index <= node.value, we are done
  if (index <= node.value) {
    return node.value;
  }
  // If index > node.value, we want to find the node right after the current node in an infix ordering of the tree
  // To do this, while we are the right child of our parent, we go up
  while (node == node.parent.right) {// node.parent can't be null, by (1)
    node = node.parent;
  }
  // here, node == node.parent.left and the leaf we started at is node.right.right.[...].right so the leaf is the last node in the infix traversal of node.parent.left, and so the next node is node.parent.
  return node.parent.value;
}

(1): The only way for node.parent to become null at some point is that the leaf we started at is root.right.[...].right. We know that its value will be n-1, and that all other values will be smaller. In particular, if the index we have to myfind wasn't absurd, it was such that index <= n-1 and so we returned at line 20.

---

The method of building two data structures for a signature and combining them can be used in many contexts: if you have two implementations of an interface with complexities (and a complexity of $+\infty$ to mean that the method is not implemented), you can combine them by taking both underlying structures, making "set" operations act on both (so that their complexity is the sum of the complexities of the two previous implementations) and the "get" operations use the fastest implementation of the two (so that the complexity is the min of the two complexities of the two previous implementations).