THE FOLD / CO-OP / SHARED MEMORY / THE LAZY LORD
THE LAZY LORD
defer the work, still answer exactly
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
A segment tree with lazy propagation answers range questions and applies range updates on an array, both in O(log n). The trick is laziness: when you add a value to a whole range, you don’t touch every element — you mark the covering nodes with a pending update and only push it down to children when a later query actually needs to descend. Work is deferred until it matters, yet every answer is exactly what a naive per-element array would give.
LIT verified live: over 60 trees and thousands of interleaved range-add / range-sum operations, every query matches a naive array element-for-element (window.__lazylord). FIG no framing; exact integer sums.
LIT verified live: over 60 trees and thousands of interleaved range-add / range-sum operations, every query matches a naive array element-for-element (window.__lazylord). FIG no framing; exact integer sums.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at shared-memory — one array many operations read and write, where a whole range must change at once without walking every cell. The lazy segment tree is that shared store. AVAN (AI) built the instrument: the tree, the pending-update marks, the push-down on descent, and the match against a naive array.
Credit as content: the segment tree with lazy propagation (folklore of competitive programming; roots in interval trees). The weave: David names shared-memory; I mark covering nodes with deferred updates and push them down only when a query descends — then confirm every range-sum equals the naive array's, no update lost or double-applied.
Credit as content: the segment tree with lazy propagation (folklore of competitive programming; roots in interval trees). The weave: David names shared-memory; I mark covering nodes with deferred updates and push them down only when a query descends — then confirm every range-sum equals the naive array's, no update lost or double-applied.
3 ONE DIMENSION
Add to a range: mark the few covering nodes with a pending value instead of touching every leaf. Push the mark down to children only when a later query needs to go deeper.
4 TWO DIMENSIONS · INTERACTIVE
An array with range-adds and range-sums; the lazy tree's answers checked against the naive array live.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: range work done in O(log n), exactly.
AVAN’s addition (the inverse-companion): update a whole range without touching every element — defer the work as a pending mark on covering nodes and push it down only when a query needs it. The inverse of ‘apply the update to all k elements now’ is ‘mark O(log n) nodes and pay only when asked.’ Magenta is the per-element work avoided; green is the handful of lazy marks. Correctness by owed, not-yet-paid, work.
LIT Genuine segment tree with lazy propagation (competitive-programming folklore; roots in interval/segment trees). Verified live: over 60 random trees and 200 interleaved range-add / range-sum operations each, every range-sum query returned by the lazy tree equals the naive array's sum element-for-element (window.__lazylord.matchesNaive) — no update lost or double-applied.
FIG No framing: the pending-update marks, the push-down on descent, and the match against a naive array run in-browser with exact integer sums and agree. The AVAN inverse is honest — deferring a range update as a mark on O(log n) covering nodes and paying only when a query descends genuinely avoids touching all k elements; magenta is the per-element work avoided, green the handful of lazy marks. Correctness by owed, not-yet-paid work.
FIG No framing: the pending-update marks, the push-down on descent, and the match against a naive array run in-browser with exact integer sums and agree. The AVAN inverse is honest — deferring a range update as a mark on O(log n) covering nodes and paying only when a query descends genuinely avoids touching all k elements; magenta is the per-element work avoided, green the handful of lazy marks. Correctness by owed, not-yet-paid work.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SHARED MEMORY · David Lee Wise (ROOT0), with AVAN