segment-tree-builder
npx machina-cli add skill a5c-ai/babysitter/segment-tree-builder --openclawSegment Tree Builder Skill
Purpose
Generate customized segment tree implementations for various merge functions, with support for lazy propagation and advanced variants.
Capabilities
- Generate segment tree for custom merge functions
- Lazy propagation template generation
- Persistent segment tree variants
- 2D segment tree generation
- Segment tree beats for complex updates
- Iterative vs recursive implementations
Target Processes
- segment-tree-implementation
- range-query-optimization
- data-structure-implementation
Segment Tree Variants
- Basic: Point update, range query
- Lazy Propagation: Range update, range query
- Persistent: Version history preservation
- 2D Segment Tree: 2D range queries
- Segment Tree Beats: Complex range updates (chmin, chmax)
- Merge Sort Tree: Range order statistics
Input Schema
{
"type": "object",
"properties": {
"mergeFunction": { "type": "string" },
"identity": { "type": "string" },
"updateType": {
"type": "string",
"enum": ["point", "range", "both"]
},
"lazyPropagation": { "type": "boolean" },
"variant": {
"type": "string",
"enum": ["basic", "lazy", "persistent", "2d", "beats"]
},
"language": {
"type": "string",
"enum": ["cpp", "python", "java"]
},
"style": {
"type": "string",
"enum": ["recursive", "iterative"]
}
},
"required": ["mergeFunction", "identity"]
}
Output Schema
{
"type": "object",
"properties": {
"success": { "type": "boolean" },
"code": { "type": "string" },
"complexity": { "type": "object" },
"usage": { "type": "string" }
},
"required": ["success", "code"]
}
Source
git clone https://github.com/a5c-ai/babysitter/blob/main/plugins/babysitter/skills/babysit/process/specializations/algorithms-optimization/skills/segment-tree-builder/SKILL.mdView on GitHub Overview
Segment Tree Builder creates tailored segment tree implementations around a user-defined merge function and identity. It supports advanced variants such as lazy propagation, persistence, 2D trees, and segment tree beats, enabling efficient range queries and updates for varied workloads. You can choose between recursive or iterative styles and target cpp, python, or java.
How This Skill Works
Provide a mergeFunction and identity, plus optional flags for variant, update type, language, and style. The builder then generates code with the appropriate update and query logic (point or range updates, lazy propagation, persistence, 2D, or beats). Output can be in C++, Python, or Java, with either recursive or iterative implementations as requested.
When to Use It
- You need range queries with a custom merge function.
- You require range updates and fast queries via lazy propagation.
- You need versioned data with a persistent segment tree.
- You have 2D range queries on a grid.
- You need advanced updates like beats (chmin/chmax) or merge-sort-tree statistics.
Quick Start
- Step 1: Define your mergeFunction and identity in the input schema.
- Step 2: Choose a variant (basic, lazy, persistent, 2d, beats), update type, language, and style.
- Step 3: Generate the code and integrate with sample queries to validate correctness.
Best Practices
- Clearly define mergeFunction and identity to match your problem’s semantics.
- Start with the Basic variant to verify correctness before enabling lazy or beats.
- Prefer iterative implementations for tight performance-sensitive code.
- Test edge cases: empty ranges, full-range updates, and identity behavior.
- Benchmark memory and time, especially for persistent and 2D variants.
Example Use Cases
- Range sum with lazy range add using the Lazy variant.
- Point updates and range maximum queries with a Basic segment tree.
- Persistent segment tree to answer offline range queries across versions.
- 2D segment tree for grid-based range queries in image processing.
- Segment Tree Beats handling chmin/chmax updates on arrays.
