Build
Bottom-up: leaves are singletons. Internal = merge children (like merge sort). O(N log N) total.
Advertisement
Range count < K
At each covered node, binary search for K in its sorted list. Sum counts.
Advertisement
Range kth smallest
Binary search on answer + range count. O((log N)³) total. Persistent segment tree does it in O((log N)²).
Space
O(N log N) — every element stored in O(log N) nodes.