Building the Wavelet Tree

To build a wavelet tree:

function buildWavelet(arr, lo, hi)
    if lo = hi then
        return leaf node

    mid := (lo + hi) / 2
    node := new WaveletNode(lo, hi)

    // Build bitvector: 0 if value <= mid, 1 if value > mid
    leftArr := []
    rightArr := []
    for val in arr
        if val <= mid then
            node.bitvector.append(0)
            leftArr.append(val)
        else
            node.bitvector.append(1)
            rightArr.append(val)

    node.left := buildWavelet(leftArr, lo, mid)
    node.right := buildWavelet(rightArr, mid + 1, hi)
    return node

Time: $O(n \log \sigma)$. Space: $O(n \log \sigma)$ for all bitvectors.