THE FOLD / CO-OP / THE PULL REQUEST / THE INTERVAL TREE
THE INTERVAL TREE
query which intervals overlap fast
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
An interval tree answers “which stored intervals overlap this query interval?” quickly, by augmenting a binary search tree. Nodes are keyed by each interval’s left endpoint; every node also caches the maximum right endpoint in its subtree. That cache lets a query prune whole branches: if a subtree’s max-high is below the query’s low, nothing there can overlap, so skip it. What would be a scan of every interval becomes a guided descent.
LIT verified live: over 2000 random interval sets and queries, the tree returns exactly the intervals a brute-force scan finds (window.__intervaltree). FIG no framing; exact overlap tests and set comparison.
LIT verified live: over 2000 random interval sets and queries, the tree returns exactly the intervals a brute-force scan finds (window.__intervaltree). FIG no framing; exact overlap tests and set comparison.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-pull-request — overlapping ranges drawn together; the interval tree pulls in exactly the intervals that intersect a query and leaves the rest. AVAN (AI) built the instrument: the left-endpoint BST keyed nodes, the max-high subtree augmentation, the prune-by-max-high query, and the match against a brute scan.
Credit as content: the interval tree (augmented BST; Cormen–Leiserson–Rivest–Stein). The weave: David names the-pull-request; I key intervals by their left endpoint, cache each subtree’s maximum right endpoint, and answer overlap queries by descending only where the cache permits — confirming the result exactly matches scanning every interval.
Credit as content: the interval tree (augmented BST; Cormen–Leiserson–Rivest–Stein). The weave: David names the-pull-request; I key intervals by their left endpoint, cache each subtree’s maximum right endpoint, and answer overlap queries by descending only where the cache permits — confirming the result exactly matches scanning every interval.
3 ONE DIMENSION
Each node stores its interval and the max right-endpoint below it. A query skips any subtree whose max-high is below the query’s low — nothing there can reach the query.
4 TWO DIMENSIONS · INTERACTIVE
Intervals as bars with a query range; the overlapping ones highlighted, checked against a brute scan.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: overlaps found without scanning all.
AVAN’s addition (the inverse-companion): find overlapping intervals without testing every one — cache each subtree’s maximum right endpoint and prune any branch that cannot reach the query. The inverse of ‘scan all intervals for overlap’ is ‘descend a BST, skipping subtrees whose max-high falls short.’ Magenta is the full scan; green is the pruned descent. Overlap queries by cached reach.
LIT Genuine interval tree (augmented BST; Cormen–Leiserson–Rivest–Stein). Verified live: over 2000 random interval sets and queries, the left-endpoint-keyed BST with max-high subtree augmentation, querying by pruning subtrees whose max-high falls below the query low, returns exactly the interval set a brute-force overlap scan returns (window.__intervaltree.matchesBrute).
FIG No framing: the keyed BST nodes, the max-high augmentation, the prune-by-max-high query, and the match against a brute scan run in-browser with exact overlap tests and agree. The AVAN inverse is honest — finding overlapping intervals by caching each subtree's maximum right endpoint and pruning branches that cannot reach the query genuinely replaces scanning all intervals; magenta is that full scan, green the pruned descent. Overlap queries by cached reach.
FIG No framing: the keyed BST nodes, the max-high augmentation, the prune-by-max-high query, and the match against a brute scan run in-browser with exact overlap tests and agree. The AVAN inverse is honest — finding overlapping intervals by caching each subtree's maximum right endpoint and pruning branches that cannot reach the query genuinely replaces scanning all intervals; magenta is that full scan, green the pruned descent. Overlap queries by cached reach.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE PULL REQUEST · David Lee Wise (ROOT0), with AVAN