Order Statistics on Ranges

Order statistics on a range ask for the k-th smallest/largest in a[l..r]—persistent segtree on compressed values or policy-based BST.

Why this shows up in the real world

Time-series dashboards, game leaderboards, and competitive programming interval problems all need fast answers on changing arrays.

Core idea (explained for students)

Walk tree comparing counts in left child vs k; O(log n) per query with persistence.

Try this in Python

def kth_smallest_brute(arr: list[int], l: int, r: int, k: int) -> int:
    return sorted(arr[l : r + 1])[k - 1]


print(kth_smallest_brute([7, 2, 5, 4], 0, 3, 2))

Common mistakes

• Using global k-th instead of subarray k-th.
• Off-by-one in k (1-based vs 0-based).

Key takeaways

• Compress coordinates of all array values.
• Count in left = how many ≤ mid in range.