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

$ curl repovive.com/roadmaps/data-structures/persistent-data-structures/kth-number-implementation

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

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

$ curl repovive.com/roadmaps/data-structures/persistent-data-structures/kth-number-implementation

Repovive

Kth Number: Implementation - Persistent Data Structures | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Kth Number: Implementation

Walk two trees together

function kth(nodeL, nodeR, l, r, k)
    // nodeL = root of version L
    // nodeR = root of version R+1
    if l = r then
        return l  // found the value

    mid := (l + r) / 2
    leftCount := nodeR.left.count - nodeL.left.count

    if k <= leftCount then
        return kth(nodeL.left, nodeR.left, l, mid, k)
    else
        return kth(nodeL.right, nodeR.right, mid + 1, r, k - leftCount)

You walk down both trees simultaneously, comparing their counts to traverse.

To answer "kth in range $[L, R]$ ":

answer := kth(roots[L], roots[R + 1], 0, maxVal, k)

Time: $O(\log n)$ per query. Space: $O(n \log n)$ total.