An *order-statistics tree* is an augmented (see AugmentedDataStructures) version of a BinarySearchTree that supports the additional operations `Rank(x)`, which returns the rank of `x` (i.e., the number of elements with keys less than or equal to x) and `FindByRank(k)`, which returns the `k`-th smallest element of the tree.

To construct an order-statistics tree, start with a tree that keeps track of the number of nodes in each subtree, using the techniques described in AggregateQueries. Let's suppose that each node has an extra field `count` that counts its descendants (including itself). Then we can implement `Rank` by a simple DecreaseAndConquer algorithm similar to the `SumAtLeast` procedure from AggregateQueries.

Rank(root, x): if root is null: error: not found else if x < root.key: return Rank(root.left, x) else if x = root.key: if root.left is not null: return root.left.count + 1 else: return 1 else if x > root.key: if root.left is not null: return root.left.count + 1 + Rank(root.right, x) else: return 1 + Rank(root.right, x)

`FindByRank` has a similar structure:

FindByRank(root, k): if root is null: error: not found if root.left is null: leftcount = 0 else: leftcount = root.left.count if k <= leftcount: return FindByrank(root.left, k) else if k = leftcount + 1: return root else if k > leftcount + 1: return FindByRank(root.right, k - leftcount - 1)

It is easy to see that both operations take O(log n) time provided the tree is balanced.