core idea: if you have segment trees for prefixes, you can answer range queries by subtraction. Let = segment tree counting elements in . Count of value in range : . For -th smallest:
At each node, compute how many elements go to left subtree in range
If , answer is in left subtree
Otherwise, answer is in right subtree with This is binary search on the value space, guided by counts from two versions.