Kth Smallest: Merge Sort Tree

Another approach: merge sort tree with binary search.

Build a segment tree where each node stores the sorted subarray for its range.

function kthSmallest(l, r, k)
    // Binary search on value
    lo := min(A), hi := max(A)
    while lo < hi
        mid := (lo + hi) / 2
        count := countLessOrEqual(l, r, mid)
        if count < k then
            lo := mid + 1
        else
            hi := mid
    return lo

countLessOrEqual uses the segment tree: at each node, binary search in the sorted array.

Time: $O(\log n \cdot \log^2 n)$ per query (two extra $\log$ factors vs wavelet tree).

Space: $O(n \log n)$.