Persistent range MEX: search last occurrences in prefix versions

Last updated: 5 Oct 20269 min read

tutorial

The minimum excluded value, or MEX, of a range is its smallest nonnegative integer that does not occur there. This static index builds a persistent segment tree over candidate values from zero through N, where N is the array length. Version r records the last zero-based position at which each candidate appeared before array position r; unseen candidates hold minus one. A query over [l,r) inspects version r and descends toward the leftmost value whose last occurrence is less than l. Each internal node stores the minimum last occurrence in its value interval, so a whole child interval can be skipped when all its values occurred inside the requested range. Each update path-copies nodes and keeps previous roots unchanged. Negative values and values above N cannot affect the MEX of a length-at-most-N range and are ignored. The input array is frozen after construction; this is not an online point-update index.

Operational case

For readings [0,3,1,0,2,7,1], the first five positions contain 0, 1, 2, and 3, so their MEX is 4. Positions [2,7) contain 1, 0, 2, 7, and 1; their MEX is 3. An empty range has MEX zero. The example builds eight prefix roots, including the empty prefix, even though only seven observations exist. Value 7 is tracked because the candidate domain is zero through seven, but it does not change these answers. A query must use root r, not root l, because root r holds the most recent occurrences before the right endpoint.

Working Python program

class PersistentRangeMex:
    def __init__(self, readings):
        self.size = len(readings)
        self.roots = [None]
        for position, reading in enumerate(readings):
            previous = self.roots[-1]
            if isinstance(reading, int) and 0 <= reading <= self.size:
                previous = self._replace(previous, 0, self.size + 1, reading, position)
            self.roots.append(previous)

    @staticmethod
    def _minimum(node):
        return -1 if node is None else node[0]

    def _replace(self, node, left, right, target, position):
        if right - left == 1:
            return position, None, None
        middle = (left + right) // 2
        old_left, old_right = (None, None) if node is None else (node[1], node[2])
        if target < middle:
            old_left = self._replace(old_left, left, middle, target, position)
        else:
            old_right = self._replace(old_right, middle, right, target, position)
        return min(self._minimum(old_left), self._minimum(old_right)), old_left, old_right

    def mex(self, start, stop):
        if not 0 <= start <= stop <= self.size:
            raise IndexError("query must be a valid half-open range")
        node, left, right = self.roots[stop], 0, self.size + 1
        while right - left > 1:
            middle = (left + right) // 2
            left_child = None if node is None else node[1]
            if self._minimum(left_child) < start:
                node, right = left_child, middle
            else:
                node, left = (None if node is None else node[2]), middle
        return left


if __name__ == "__main__":
    index = PersistentRangeMex([0, 3, 1, 0, 2, 7, 1])
    print(index.mex(0, 5), index.mex(2, 7), index.mex(4, 4))
    print(len(index.roots))

Output

4 3 0
8

Time, space, and tradeoff

Each eligible observation copies O(log N) nodes in its prefix version. Construction therefore costs O(N log N) time and O(N log N) retained nodes in the worst case, plus O(N) root references; ignored values reuse the preceding root. A valid range query follows one branch per value-tree level in O(log N) time and O(1) auxiliary space. The Python tuple representation adds object overhead and recursive construction uses O(log N) call depth. A direct scan with a temporary set costs O(range length) time and space and can be better for a few small queries. Persistence pays when many ranges in one immutable array need independent right-endpoint snapshots.

Common Mistakes

Do not search the version at the left endpoint instead of the right endpoint.
Do not treat a last occurrence equal to l as absent from [l,r).
Do not mutate nodes shared by earlier prefix roots.
Do not assume values above the array length can change its range MEX.

Connected lessons

Compare this operation boundary with Range XOR bases: merge linear spans in a segment tree, Affine lazy segment trees: compose range calibration before summing, Min-max heaps: remove either end of one dispatch priority array, then complete the audit project and decision quiz.

Persistent subarray ranks: subtract prefix frequency trees examines a related structure with a different operation boundary.

Persistent range-distinct counts: keep only the latest position active examines a related structure with a different operation boundary.

data structures

range-query-structures