augmenting-data-structures

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.