• 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