1 Introduction
1.1 Model and Results
1.2 Example Scenarios
1.3 Advantages
1.4 Disadvantages
1.5 Paper Organization
2 Related Work
2.1 Deferred Data Structures
2.2 Online Dynamic Multiple Selection
2.3 Dynamic Optimality
3 Technical Overview
4 Rank-Based Queries
5 Lower and Upper Bounds
6 Data Structure
6.1 The Gap Data Structure
6.2 The Interval Data Structure
6.3 Representation of Intervals
6.4 Insertion
6.5 Query
6.6 Deletion
6.7 Change-Key
7 Analysis
7.1 Insertion
7.2 Query
7.2.1 Current Query
7.2.2 Ensuring Invariant (C)
7.2.3 0-Sided and 1-Sided Gaps
7.3 Deletion
7.4 Change-Key
7.5 Pointer Bound and Improved Insertion and Change-Key
8 Bulk Update Operations
9 Average Case Insertion and Change-Key
9.1 Insert
9.2 Change-Key
10 Randomized-Selection Variant
11 Lazy Splay Trees
11.1 Splay Trees For The Gap Data Structure
11.2 Efficient Access Theorems
12 Conclusion and Open Problems
References