Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 14

The authors, in this chapter, describe how red-black trees can be modified to get any order statistic as well as rank of an element in $ O(\lg n) $ time. The rank of a node is defined as its position in the linear order of the set. The authors define order-statistic tree T as a tree where each node, besides maintaining the usual information about left-child, right-child, parent, key and color, also maintains size, which is the number of internal nodes (including the node itself) in the sub-tree rooted at that node.

The authors provide algorithms to find an element with rank $i$ and also determine rank of an element $x$ in an order statistic tree T and prove that both take a running time of $ O(\lg n) $. The authors then also modify the original INSERT and DELETE operations on RED-BLACK TREE to maintain the size information in each node and proves that it does not impact their running time.

The authors then provide a description of augmenting current data structures and prove some that this augmentation does not result in an increase in running time of the operations defined on the original data structure if the change in the extra data only affects the ancestors or descendants of the affected node.

The authors then define closed, open, half-open intervals, overlap, low-endpoint and high-endpoint.

The authors then define an interval tree by modifying RED-BLACK TREE, describe the extra information that need to be put in each node and define operations like INSERT, DELETE and SEARCH on it.