K-th Order Statistics on Ranges

“What is the $k$-th smallest element of $a[l..r]$?” — and its relatives: rank, count in a value range, median.

The methods

Method	Preprocess	Query	Memory	Updates	Online
Sort the range	—	$O(n\log n)$	$O(1)$	✔	✔
nth_element on a copy	—	$O(n)$	$O(n)$	✔	✔
Merge sort tree + binary search	$O(n\log n)$	$O({\log }^{3}n)$	$O(n\log n)$	✘	✔
Persistent segment tree	$O(n\log n)$	$O(\log n)$	$O(n\log n)$	✘	✔
Wavelet tree	$O(n\log C)$	$O(\log C)$	$O(n\log C)$ bits	✘	✔
Offline: sort by value + BIT	—	$O(\log n)$ am.	$O(n)$	✔	✘
Mo’s + a value BIT	—	$O(\sqrt{n}\log n)$	$O(n)$	✘	✘
Parallel binary search + BIT	—	$O({\log }^{2}n)$ am.	$O(n)$	✔	✘
BIT of sorted vectors (“BIT-of-BIT”)	$O(n\log n)$	$O({\log }^{3}n)$	$O(n\log n)$	✔	✔

The two to know: persistent segment tree (online) and the offline BIT sweep (simpler, less memory).

Persistent segment tree — the online answer

Build version $i$ by inserting $a_i$ into version $i-1$, with the tree indexed by value. Then version $r$ minus version $l-1$ is a segment tree over exactly the values in $a[l..r]$, and descending it finds the $k$-th smallest.

int kth(int u, int v, int lo, int hi, int k) {         // u = root[l-1], v = root[r]
    if (lo == hi) return lo;
    int leftCount = cnt[left[v]] - cnt[left[u]];
    int mid = (lo + hi) / 2;
    if (k <= leftCount) return kth(left[u],  left[v],  lo, mid, k);
    else                return kth(right[u], right[v], mid+1, hi, k - leftCount);
}

$O(\log n)$ per query, $O(n\log n)$ nodes. Compress the values first.

The same structure answers:

• count of elements $\le x$ in $[l,r]$,
• count in a value range,
• sum of the $k$ smallest (store sums alongside counts),
• the median (with $k=\frac{r-l+1}{2}$).

Offline: sort by value and sweep

If the queries are known in advance, this is simpler and uses $O(n)$ memory:

// binary search the answer VALUE for all queries in parallel
// (parallel binary search), with a BIT counting positions of inserted values

Or, for “count $\le x$ in $[l,r]$” specifically, sort both the array elements and the queries by value and sweep with a BIT over positions — $O((n+q)\log n)$ time, $O(n)$ memory. See Offline Query Processing.

With updates

Point updates plus $k$-th-smallest queries need either:

• BIT of segment trees (a “2D” structure), $O({\log }^{2}n)$ per operation, $O(n{\log }^{2}n)$ memory — heavy;
• parallel binary search offline, $O({\log }^{2}n)$ amortized, $O(n)$ memory — much lighter;
• sqrt decomposition with sorted blocks, $O(\sqrt{n}\log n)$ per query, $O(B)$ to rebuild a block on update.

The offline route is nearly always the right choice in a contest.

The whole array, not a range

For “$k$-th smallest of the entire array”:

nth_element(a.begin(), a.begin() + k, a.end());        // O(n) expected
int kth = a[k];

$O(n)$ expected with introselect. For a guaranteed $O(n)$, median-of-medians exists but is slower in practice.

Related queries

Query	Method
Rank of $x$ in $[l,r]$	count of elements $<x$
Median of $[l,r]$	$k=\lceil (r-l+1)/2\rceil$
Count in the value range $[a,b]$	difference of two counts
Sum of the $k$ smallest	persistent segtree storing sums
Mode (most frequent) of $[l,r]$	different problem — $O(n\sqrt{n})$ offline, or an $O(n^2/\log )$ preprocessing
$k$-th smallest on a tree path	persistent segment tree indexed by root-path, combined with LCA
$k$-th distinct value	a distinct-count structure plus a descent

The tree-path version is a nice combination: build a persistent segment tree along each root-to-vertex path, then the multiset on the path $u\to v$ is $\mathrm{ver}[u]+\mathrm{ver}[v]-\mathrm{ver}[l]-\mathrm{ver}[\mathrm{par}(l)]$ where $l$ is the LCA — four versions descended in lockstep.

See also: Persistent Structures · Wavelet Tree · Parallel Binary Search