advanced-ds-library
Scannednpx machina-cli add skill a5c-ai/babysitter/advanced-ds-library --openclawAdvanced Data Structures Library Skill
Purpose
Provide implementations and guidance for advanced data structures commonly needed in competitive programming and complex algorithmic problems.
Capabilities
- Treaps, Splay trees, Link-cut trees
- Persistent data structures
- Wavelet trees
- Heavy-light decomposition
- Centroid decomposition
- Rope data structure
- Order statistics tree
Target Processes
- data-structure-implementation
- advanced-graph-algorithms
- cp-library-creation
Data Structure Catalog
Balanced BSTs
- Treap (randomized BST)
- Splay Tree (self-adjusting)
- AVL Tree
- Red-Black Tree
Tree Decomposition
- Heavy-Light Decomposition
- Centroid Decomposition
- Euler Tour Technique
Advanced Structures
- Link-Cut Trees (dynamic trees)
- Wavelet Tree (range queries)
- Persistent Segment Tree
- Rope (string with fast operations)
Input Schema
{
"type": "object",
"properties": {
"dataStructure": { "type": "string" },
"operations": { "type": "array" },
"language": {
"type": "string",
"enum": ["cpp", "python", "java"]
},
"includeTests": { "type": "boolean", "default": false }
},
"required": ["dataStructure"]
}
Output Schema
{
"type": "object",
"properties": {
"success": { "type": "boolean" },
"code": { "type": "string" },
"complexity": { "type": "object" },
"usage": { "type": "string" },
"applications": { "type": "array" }
},
"required": ["success"]
}
Source
git clone https://github.com/a5c-ai/babysitter/blob/main/plugins/babysitter/skills/babysit/process/specializations/algorithms-optimization/skills/advanced-ds-library/SKILL.mdView on GitHub Overview
Provides ready-to-use implementations and practical guidance for advanced data structures used in competitive programming. It covers Treaps, Splay trees, Link-Cut trees, Wavelet trees, Heavy-Light and Centroid decompositions, ropes, persistent structures, and order-statistics trees to boost algorithm performance.
How This Skill Works
The skill gathers language-specific templates and reference implementations for a spectrum of advanced data structures, organized by category (balanced BSTs, tree decompositions, and other structures). Developers adapt these templates for cp-library workflows, guided by the defined input and output schemas and test strategies.
When to Use It
- You are building a CP library and need robust, ready-to-use DS implementations.
- You tackle dynamic graph problems requiring link-cut trees or heavy-light decomposition.
- You need fast range queries and order-statistics capabilities (wavelet trees, OSTs).
- You require versioned/rollback capability with persistent data structures.
- You manage long strings or editors needing rope-based operations.
Quick Start
- Step 1: Pick a dataStructure (e.g., Treap) and a language (cpp/python/java).
- Step 2: Provide the operations array and set includeTests as needed; feed into the library to generate skeleton code.
- Step 3: Compile, run tests, and integrate into your cp-library.
Best Practices
- Start with small, battle-tested templates before adding custom tweaks.
- Benchmark time and memory on representative workloads.
- Prefer language-idiomatic idioms to maximize performance (e.g., C++ templates, Python optimizations).
- Document complexities, invariants, and edge cases for each DS.
- Use randomized testing and property-based tests to validate correctness.
Example Use Cases
- Treap-based priority queue for randomized balancing in CP.
- Link-Cut Tree for dynamic connectivity in online queries.
- Persistent Segment Tree for versioned array access.
- Rope for efficient substring operations in text processing.
- Wavelet Tree for fast range frequency queries.
