Persistent Kth Smallest

Static range $k$ -th smallest, $n$ and $q$ up to $2 \cdot 10^5$ , built from a persistent segment tree over the value domain. What does it cost and why?

$O(n^2)$ nodes and $O(\log n)$ per query. Each prefix version copies the whole tree of $O(n)$ nodes, and the query descends the difference of versions $r$ and $l-1$ .

$O(n \log n)$ nodes and $O(\log n)$ per query. Each prefix version copies only the $O(\log n)$ nodes on one root-to-leaf path, and the query descends the difference of versions $r$ and $l-1$ .

$O(n)$ nodes and $O(\log n)$ per query. Each prefix version copies only the one changed leaf and shares every ancestor, and the query descends the difference of versions $r$ and $l-1$ .

$O(n \log n)$ nodes and $\Theta(\log^2 n)$ per query. Each prefix version copies only the $O(\log n)$ nodes on one root-to-leaf path, and the query binary searches the value domain, descending once per step.