Kth Number: The Idea

Core idea: if you have segment trees for prefixes, you can answer range queries by subtraction. Let $T_i$ = segment tree counting elements in $A[0..i-1]$. Count of value $v$ in range $[l, r]$: $T_{r+1}[v] - T_l[v]$. For $k$-th smallest:

$1.$ At each node, compute how many elements go to left subtree in range $[l, r]$

$2.$ If $k \leq \text{leftCount}$, answer is in left subtree

$3.$ Otherwise, answer is in right subtree with $k - \text{leftCount}$

This is binary search on the value space, guided by counts from two versions.