What is an Augmented Data Structure?

What is an Augmented Data Structure?

Approach: Describe adding extra information to nodes of a standard data structure.

A standard data structure that is extended with additional information to support new operations. For example, a BST where each node stores the size of its subtree to find the i-th element.

Follow-up: What is an Order Statistic Tree?

Key concepts: size, order statistic tree, dynamic.