patternMinor
Union-Find with link-by-rank to represent a binary field with simple operations
Viewed 0 times
fieldsimpleoperationsrankrepresentwithunionbinaryfindlink
Problem
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?
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?
Solution
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.
Context
StackExchange Computer Science Q#89472, answer score: 4
Revisions (0)
No revisions yet.