Overview
An Order Statistic Tree is a balanced binary search tree that stores additional information, usually the size of each subtree. This information allows the structure to answer order-related queries, such as finding the kth smallest element or calculating how many elements are smaller than a given value.
How it works
Each node stores a key and the size of its subtree.; The left subtree contains keys smaller than the current node in a standard binary search tree.; The size of the left subtree determines the current node's sorted position relative to its subtree.; A kth-smallest query compares k with the size of the left subtree.; The algorithm moves left, returns the current node, or moves right with an adjusted rank.; After insertion or deletion, subtree sizes must be updated.
Key concepts
Balanced binary search trees; Subtree sizes; Order statistics; Rank queries; Kth-smallest selection; Tree augmentation
Time complexity
operation: Select kth element; complexity: O(log n) in a balanced tree; operation: Rank query; complexity: O(log n) in a balanced tree; operation: Insertion; complexity: O(log n) in a balanced tree; operation: Deletion; complexity: O(log n) in a balanced tree
Space complexity
O(n), with additional subtree-size information stored in each node.
Example
sortedElements: 10; 20; query: Find the 4th smallest element.; result: 40; rankQuery: Find the number of elements smaller than 50.; rankResult: 4
Applications
Finding kth smallest or largest elements; Dynamic ranking systems; Median maintenance; Order-based database queries; Counting values smaller than a given key; Competitive programming