Kth Number: Building

Build persistent segment tree version by version:

function build(arr)
    // Coordinate compress
    sorted := sort(unique(arr))
    rank := map value to index
    maxVal := len(sorted) - 1

    // Empty tree as version 0
    roots := [buildEmpty(0, maxVal)]

    // Add elements one by one
    for i from 0 to len(arr) - 1
        r := rank[arr[i]]
        newRoot := update(roots[i], 0, maxVal, r, +1)
        roots.append(newRoot)

    return roots

Version $i$ represents prefix $A[0..i-1]$.

Version 0 is empty.

Version $n$ contains all elements.