# Augmenting Data Structures

> Use when augmenting balanced trees or dynamic sets with maintained metadata, order-statistic trees, interval trees, rank/select queries, overlap search, red-black-tree augmentation theorems, or production choices around custom indexed structures.

- **Type:** Skill
- **Install:** `agentstack add skill-arcadi4-nerdy-augmenting-data-structures`
- **Verified:** Yes — security-reviewed for prompt injection and unsafe behavior
- **Seller:** [Arcadi4](https://agentstack.voostack.com/s/arcadi4)
- **Installs:** 0
- **Category:** [Search](https://agentstack.voostack.com/c/search)
- **Latest version:** 0.1.0
- **License:** MIT
- **Upstream author:** [Arcadi4](https://github.com/Arcadi4)
- **Source:** https://github.com/Arcadi4/nerdy/tree/main/clrs/augmenting-data-structures

## Install

```sh
agentstack add skill-arcadi4-nerdy-augmenting-data-structures
```

Requires the [AgentStack CLI](https://agentstack.voostack.com/docs/cli). Works with Claude Code, Cursor, and any MCP-compatible agent.

## About

# Augmenting Data Structures

## Overview

Augmenting a data structure is not "add a cached field and hope." The reusable move is to choose a base structure whose ordinary operations already fit the access pattern, add metadata whose dependencies are local enough to maintain, prove mutation updates preserve it, and only then design new queries that safely exploit it.

For production use, treat the textbook structures as proof patterns and API design warnings. Prefer mature ordered containers, database range indexes, exclusion constraints, or tested libraries unless the custom metadata and workload justify owning rotations, deletion, concurrency, persistence, and rebuild logic.

## Shared CLRS Conventions

Follow the parent `clrs` skill for mathematical formatting, formula-free headings, direct polished answers, and CLRS-wide answer style. Keep identities, inequalities, bounds, and recurrence-like claims in display LaTeX blocks rather than inline prose.

## When to Use

Use this skill for:

- Designing or reviewing augmented dynamic sets, especially red-black trees with per-node metadata.
- Order-statistic trees, `OS-SELECT`, `OS-RANK`, select-by-rank, rank-by-handle, inversion counting, Josephus-style rank deletion, or multiset rank APIs.
- Interval trees, interval overlap search, booking conflict detection, rectangle sweep-line active sets, or endpoint-overlap reasoning.
- Applying the red-black-tree augmentation theorem and checking whether a candidate attribute is locally maintainable.
- Explaining why rotations can update metadata locally and why some metadata depends on ancestors instead.

Do **not** use this skill merely because code contains cached fields. Use ordinary implementation judgment unless the cache is maintained across dynamic-set mutations and participates in asymptotic query behavior or proof obligations.

## The Four-Step Augmentation Method

Use this as the default design and review checklist:

1. **Choose the underlying structure.** It should already support the ordering, search, insertion, deletion, and traversal pattern needed by the application.
2. **Choose the extra information.** Define exactly what each field means, including sentinel or empty-subtree values.
3. **Verify maintainability.** Show how every modifying operation updates the field without breaking the claimed bound, especially rotations and deletion moves.
4. **Develop the new operations.** Prove the query uses the metadata safely; do not assume pruning is safe because it is intuitive.

If any step is vague, stop. The augmentation is not ready for implementation review.

## First Decision: Should This Be a Custom Augmented Tree?

| Need | Prefer | Reason |
| --- | --- | --- |
| Exact lookup only | Hash table or existing dictionary | Augmented order adds complexity without value. |
| Ordered iteration plus rank/select | Existing order-statistic container if available; otherwise balanced tree with subtree counts | Rank needs maintained subtree cardinalities and duplicate semantics. |
| Time booking conflicts | Database constraint, range index, or interval library before custom tree | Transactions, persistence, and boundary semantics are often harder than overlap search. |
| One-off static interval queries | Sort, sweep line, segment tree, or static interval index | Dynamic deletion and rotations may be unnecessary. |
| Educational proof or specialized in-memory index | Custom augmented balanced tree | Only when invariants, tests, concurrency, and maintenance ownership are explicit. |
| External-memory or storage-engine index | B-tree-like or database-native structure | Pointer red-black trees do not model page, disk, or cache behavior. |

Before approving custom code, require explicit answers for interval openness, duplicate keys, object handles, iterator invalidation, concurrent writers, persistence, rebuilds after corruption, and test coverage for stale metadata.

For interval trees specifically, duplicate low endpoints require a deterministic secondary ordering or bucket policy. Equal low endpoints can be ordered by high endpoint plus stable identifier, stored in a per-low bucket, or represented by handles that define identity outside the comparator.

## Augmentation Theorem for Red-Black Trees

Theorem 17.1 applies when a node's augmented attribute can be computed in constant time from the node itself and its children, including their augmented attributes. Then insertion and deletion can maintain the attribute without changing the asymptotic red-black-tree bounds.

Use this theorem only after checking:

1. The attribute's definition is per subtree, not per root-to-node path unless ancestor data is explicitly maintained elsewhere.
2. The value at a node depends only on that node and its two children.
3. The sentinel or empty-child value is defined.
4. Rotations invalidate only the nodes whose child sets change, or any propagation remains bounded by the tree height and the constant number of rotations.
5. Deletion's moved node and all ancestors on changed paths are handled.

Examples that satisfy the local condition:

- Subtree size for order-statistic trees.
- Maximum high endpoint in an interval subtree.
- Black-height, when represented from descendants and node color. Define the sentinel black-height convention first, then compute a node's value from one child black-height plus the node's color, relying on the red-black equal-black-height invariant.
- Any associative inorder aggregate that can be combined from left aggregate, node payload, and right aggregate.

Examples that do not satisfy the theorem directly:

- Node depth, because it depends on ancestors and rotations can change depths for many descendants.
- Global rank stored directly in every node, because inserting a new minimum can change many ranks.
- Metadata whose value depends on sibling, parent, or external global state unless an additional proof bounds updates.

## Order-Statistic Trees

An order-statistic tree is a red-black tree with a subtree-size field at each node. The sentinel's size is zero, and every internal node satisfies the identity below.

$$
x.\mathrm{size}=x.\mathrm{left}.\mathrm{size}+x.\mathrm{right}.\mathrm{size}+1
$$

This metadata supports two different query shapes:

| Query | Input contract | Core move |
| --- | --- | --- |
| Select by rank | Tree root and a one-based rank within the subtree | Compare the target rank with the left-subtree size plus one. |
| Rank by node | A tree and a node handle already in the tree | Start with the node's local rank and climb to the root, adding skipped left subtrees when moving up from a right child. |

For select, at a node compute the rank of that node within its own subtree.

$$
r=x.\mathrm{left}.\mathrm{size}+1
$$

Then go left, return the node, or go right with the target rank reduced by the local rank.

For rank, initialize with the node's local rank. While climbing to the root, add the parent and the parent's left subtree exactly when the climb comes from a right child.

### Duplicate-Key Discipline

Do not say `rank(key)` is well-defined in a multiset unless the API defines which equal key is meant. The textbook node-rank operation takes a node pointer, and with duplicate keys the rank is the node's position in inorder traversal, not a unique property of the key value.

Production choices include:

- `rank(handle)`: caller identifies the exact node or iterator.
- `rank_lower_bound(key)`: count elements strictly below the key.
- `rank_upper_bound(key)`: count elements at or below the key.
- Compound ordering by key plus stable tie-breaker.
- One node per key with a multiplicity count and explicit within-bucket offset rules.

Concrete API patterns:

```text
select(index) -> handle
rank(handle) -> index of that exact element
count_less_than(key) -> lower-bound rank
count_at_most(key) -> upper-bound rank
insert(key, value) -> handle with stable tie-breaker or bucket offset
```

Choose one policy before writing tests. Searching by key and then calling node-rank is ambiguous if search may return any duplicate.

### Maintaining Subtree Size

Insertion increments the size field on the downward search path and gives the new node size one. Rotation repair changes only local child sets, so update the two rotated nodes in dependency order.

For a left rotation around the old parent, the new parent inherits the old parent's subtree size, and the old parent recomputes from its children.

Deletion decrements sizes along the changed path from the lowest moved or removed position toward the root, then handles fixup rotations the same way. The important review point is not the exact pseudocode line number; it is that every structural path change and every rotation has a metadata update rule.

## Interval Trees

An interval tree stores intervals in a red-black tree ordered by low endpoint. Each node also stores the maximum high endpoint among all intervals in its subtree. The empty subtree value must be below every valid high endpoint or be represented as a sentinel-safe minimum.

$$
x.\mathrm{max}=\max\{x.\mathrm{int}.\mathrm{high},x.\mathrm{left}.\mathrm{max},x.\mathrm{right}.\mathrm{max}\}
$$

Closed intervals overlap when both endpoint comparisons succeed.

$$
i.\mathrm{low}\le i'.\mathrm{high}\quad\text{and}\quad i'.\mathrm{low}\le i.\mathrm{high}
$$

If using open or half-open intervals, rewrite the overlap predicate and all boundary tests before implementing. Booking systems often use half-open intervals so adjacent bookings do not conflict.

### Interval Search Rule

At node `x`, if the query does not overlap `x.int`, go left exactly when the left subtree is nonempty and its maximum high endpoint reaches the query's low endpoint. Otherwise go right.

The safe-right proof is simple: if the left subtree is empty or its maximum high endpoint is before the query's low endpoint, every interval in the left subtree ends before the query starts, so none overlaps.

The safe-left proof is the common trap. If the algorithm goes left and the left subtree contains no overlapping interval, it still does not miss a right-subtree overlap:

1. Choose a witness interval in the left subtree whose high endpoint equals the stored left-subtree maximum.
2. Since that interval does not overlap the query, interval trichotomy puts the query strictly to its left by high endpoint.
3. Because the tree is ordered by low endpoint, every right-subtree interval starts no earlier than the current node's low endpoint, which is no earlier than the left interval's low endpoint.
4. Therefore every right-subtree interval starts after the query ends, so none overlaps.

When proving correctness, name all three ingredients: interval trichotomy, existence of an interval attaining the left maximum, and BST ordering by low endpoint. Omitting any one usually turns the proof into hand-waving.

Compact contradiction template:

1. Assume some right-subtree interval overlaps the query.
2. Use low-endpoint ordering to place the current node's low endpoint at or before the query's high endpoint.
3. Pick the left-subtree witness whose high endpoint reaches the query's low endpoint.
4. Since the witness does not overlap the query, trichotomy forces the query to end before the witness starts.
5. Low-endpoint ordering then puts every right-subtree interval after the query, contradicting the assumed overlap.

The later recursive outcome in the left subtree is not part of the pruning decision. The pruning proof is local to the node where the branch choice is made.

### Interval API and Production Boundaries

Before using an interval tree for real booking, calendars, reservations, or VLSI geometry, define:

- Closed, open, or half-open interval semantics.
- Whether zero-length intervals are valid.
- Endpoint normalization for timestamps, time zones, daylight saving transitions, and precision.
- Whether the query needs any overlap, all overlaps, the earliest-low overlap, exact interval lookup, or maximum-overlap point.
- How delete, update, reschedule, and batch import maintain the maximum endpoint metadata. Treat reschedule as delete plus insert unless the implementation has a proved in-place update path.
- How concurrent insertions avoid race conditions between search and commit. If conflict search and insertion are not one transaction or one lock-protected critical section, the structure is not sufficient for booking correctness.
- How persistence, crash recovery, and rebuilds restore both the base tree and the augmented metadata after partial writes or corrupted state.

Go/no-go rubric for custom interval trees:

- **Go** only when the workload is truly dynamic, in-memory latency matters, interval semantics are stable, the team can test rotations and deletion paths, and library/database options fail a documented requirement.
- **No-go** when correctness depends on transactions, cross-process persistence, ad hoc rebuilds, complex calendar normalization, or operational ownership the team cannot staff.
- **Prefer database or library** when a range index, exclusion constraint, geometry index, or maintained ordered container provides the same conflict rule with less bespoke metadata maintenance.

Minimum acceptance tests for a production-bound interval tree:

1. Empty tree, single node, and root replacement on delete.
2. Boundary-touching intervals under the chosen openness convention.
3. Nested intervals, identical intervals, equal low endpoints, and equal high endpoints.
4. Insert and delete sequences that force both left and right rotations.
5. Reschedule and batch-update paths compared against delete plus insert semantics.
6. Randomized operation sequences checked against a brute-force interval list.
7. Concurrency or transaction tests for simultaneous non-conflicting and conflicting bookings.
8. Rebuild or recovery tests that recompute augmented metadata from persisted base records.

## Common Extension Patterns

| Problem | Augmentation idea | Trap |
| --- | --- | --- |
| Count inversions in an array | Insert elements into an order-statistic tree and count prior larger elements | Define duplicate policy before counting. |
| Josephus permutation | Maintain remaining people by rank and repeatedly select/delete by modular rank | Indices shift after deletion; use subtree sizes rather than array deletion. |
| List all overlapping intervals | Repeatedly search and delete temporarily, or recursively prune subtrees using maximum endpoints | Restoring mutations and duplicate intervals must be safe. |
| Rectangle overlap with sweep line | Sweep by horizontal edge events and keep active vertical intervals in an interval tree | Event ordering must handle containment and boundary semantics. |
| Point of maximum interval overlap | Store endpoint deltas and augment prefix-sum information | Tie-breaking and endpoint openness change counts. |
| Minimum gap in a dynamic set | Maintain subtree minimum, maximum, and minimum adjacent gap | The gap depends on boundary values crossing child and parent regions. |

## Invariant and Proof Recipes

For an augmented red-black tree:

1. State the base BST or red-black invariant separately from the augmented invariant.
2. Define the sentinel value.
3. Show the augmented value is computed from children and local node data.
4. Show insertion/deletion update changed ancestor paths.
5. Show each rotation recomputes affected nodes in dependency order.
6. Only then analyze the new query.

For order-statistic queries:

1. Convert the desired rank convention to a node-handle, lower-bound, upper-bound, or tie-broken key contract.
2. Use left-subtree size to count inorder predecessors.
3. For upward rank, add skipped regions only when moving up from a right child.
4. State the height-bound dependency on the balanced tree.

For interval search:

1. State the interval overlap predicate and boundary convention.
2. State that the tree is ordered by low endpoint.
3. State that the maximum endpoint is a subtree aggregate.
4. Prove

…

## Source & license

This open-source skill is cataloged on AgentStack and links to its original source — we do not rehost the code.

- **Author:** [Arcadi4](https://github.com/Arcadi4)
- **Source:** [Arcadi4/nerdy](https://github.com/Arcadi4/nerdy)
- **License:** MIT

Install and usage instructions live in the source repository linked above.

## Pricing

- **Free** — Free

## Security capabilities

Automated source analysis of v0.1.0 — what this tool can access:

- **Network access:** no
- **Filesystem access:** no
- **Shell / process execution:** no
- **Environment & secrets:** no
- **Dynamic code execution:** no

*"Yes" means the capability is present in the source — more access means more to trust, not that it is unsafe.*


## Versions

- **0.1.0** — security scan: passed — Imported from the upstream source.

## Links

- Listing page: https://agentstack.voostack.com/l/skill-arcadi4-nerdy-augmenting-data-structures
- Seller: https://agentstack.voostack.com/s/arcadi4
- Browse the marketplace: https://agentstack.voostack.com/browse

---
Listed on AgentStack — the marketplace for AI agent skills and MCP servers. Every listing is security-reviewed. Creators keep 70%.