#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/wavelet-trees/kth-smallest-merge-sort-tree

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/wavelet-trees/kth-smallest-merge-sort-tree

Repovive

Kth Smallest: Merge Sort Tree - Wavelet Trees | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Kth Smallest: Merge Sort Tree

Alternative approach

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 (one extra $\log$ factor vs wavelet tree). Space: $O(n \log n)$ .