augmenting-data-structures

A guide to designing data structures that store extra information alongside items so they can answer special queries efficiently. Examples include balanced search trees that support ranking, selection, or finding overlapping ranges.

In plain words
What is it for?
Use it when building or reviewing order-statistic trees, interval trees, dynamic sets, rank and select operations, or other indexed data structures.
Why use it?
It helps keep stored metadata correct when items are inserted, deleted, or rearranged, avoiding unreliable cached values and unsafe custom structures.

Skill for Claude CodeCodex

Install

Getting it into your agent

One page per mod, every tool's command on it. A separate URL per tool would split the same page into five that compete with each other.

agentmods
npx agentmods add skills/arcadi4/nerdy/augmenting-data-structures
Any agent
npx skills add Arcadi4/nerdy --skill augmenting-data-structures
Clone the repo
git clone --depth 1 https://github.com/Arcadi4/nerdy

Made for: Claude Code, Codex.

Per session 50 Skills are progressive disclosure: only the name and description are preloaded; the body loads when the skill is used.
When invoked 3,956 The whole file, excluding the scripts and references it only reads on demand.
Security scan A 0 findings. Scan, not verified.
Origin original No closer match found in the catalogue.
Token cost

What it costs to keep this loaded

Counted locally with the o200k_base tokenizer, which is exact for GPT models; Claude uses its own tokenizer and its counts differ. Treat this as one consistent yardstick across the catalogue rather than a bill. Prices are per million input tokens.

ModelPer sessionOnce invoked
Fable 5 $0.00050 $0.03956
Opus 5 $0.00025 $0.01978
Sonnet 5 $0.00010 $0.00791
Haiku 4.5 $0.00005 $0.00396

Measured 2d ago against content hash def24a802d72, method: parsed. Prices are Anthropic first-party input rates as of 2026-08-30, from the pricing page.

Security

Grade A, and why

augmenting-data-structures scanned grade A with 0 findings against 26 rules in 11 categories — prompt injection, anti-refusal, data exfiltration, privilege escalation, supply chain, agent snooping, system-prompt leakage, SSRF and excessive agency — measured 2d ago.

A static scan of the body, not an audit. Every finding is printed with the line that produced it so you can judge whether it matters here. A mod is markdown that instructs an agent; that is exactly why what it instructs is worth reading.

Nothing flagged

None of the 26 patterns this scan looks for appear in this file: no shell pipes, no recursive deletes, no credential paths, no hidden text, no instruction-override or anti-refusal phrasing, no agent-config snooping. That is not a guarantee, it is the absence of the things that are checkable.

clrs/augmenting-data-structures/SKILL.md · 289 lines

How it starts

The opening of the file, as written. The whole thing — 289 lines — stays where its author put it; the contents beside it link to each section on GitHub.

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.

Read the full file on GitHub · 289 lines

Changes

What this file has done since we first saw it

Hashed on every crawl. A supply-chain change to an agent config is a question of when, not whether, so the history is kept rather than the latest state alone.

  1. 2d ago First seen · 289 lines · 50 tokens per session scan A def24a802d72

Subscribe to this mod's changes

augmenting-data-structures is a skill published in the GitHub repository Arcadi4/nerdy (7 stars, last pushed 4mo ago), licensed MIT. It adds 50 tokens to every session and 3,956 once invoked, about $0.0003 per session on Opus 5. A static security scan graded it A with 0 findings. No closer match exists in the catalogue, so it is treated as the original; first seen 2026-08-31.