@zakkster/lite-logn

Zero-GC, O(log n) data structures that PROVE their logarithm. The O(log n) sibling of @zakkster/lite-o1: where lite-o1 holds the constant (a flat ops/ms line), lite-logn holds the logarithm (a straight line on a log-x axis -- one added level per doubling of n). v1.5.0 ships twenty members: BinaryHeap (array-embedded O(log n) push / pop min|max heap), Fenwick / BIT (O(log n) point-update AND prefix-sum via the i & -i walk), SegmentTree (O(log n) associative range-query -- min / max / sum / gcd -- plus point-update over a flat 2n array), SkipList (pointer-free expected-O(log n) ordered map over a private free-list node pool), Treap (a randomized-balanced augmented ordered map with O(log n) rank / select / split / merge), Scapegoat (a DETERMINISTIC weight-balanced augmented ordered map: worst-case-O(log n) get, amortized-O(log n) set / delete, zero-GC rebuild), MinMaxHeap (an array-embedded double-ended priority queue: O(1) peekMin / peekMax, O(log n) push / popMin / popMax), SplayTree (a self-adjusting ordered map: amortized-O(log n) get / set / delete via top-down splay, hot keys ride near the root), BinomialHeap (a mergeable priority queue: O(log n) meld of two heaps over a shared arena, O(1)-amortized push, O(log n) popMin), PairingHeap (an ADDRESSABLE mergeable priority queue: O(1) push / meld over a shared arena, amortized-O(log n) popMin / decreaseKey / remove by arena-wide-unique id), FibonacciHeap (the textbook-optimal ADDRESSABLE mergeable priority queue: O(1)-amortized push / meld / decreaseKey, O(log n)-amortized popMin / remove), Fenwick2D (the family's FIRST 2D structure: O(log^2 n) point-update AND rectangle-sum over a flat 2D Binary Indexed Tree), SegmentTree2D (the general 2D rectangle FOLD a 2D BIT cannot do: O(log^2 n) point-update AND rectangle min / max / sum / gcd over a flat segment tree of segment trees), SortedArray (the read-optimized ordered map: O(log n) get / rank / successor / predecessor and O(1) select / keyAt / valueAt / min / max over two parallel sorted arrays, with O(n) in-place-shift writes disclosed), and PersistentSegTree (the family's FIRST persistent structure: a FULLY PERSISTENT / branching segment tree via path-copying -- update(fromVersion, i, value) returns a new version sharing every off-path subtree in O(log n), any past version stays queryable, over a monotonic bump/append node arena), and MergeSortTree (the family's FIRST truly IMMUTABLE member and FIRST offline range-RANK structure: a STATIC merge sort tree answering countLE -- how many values <= x in an index range -- and rangeCount -- how many in a value-window -- in worst-case O(log^2 n) over a segment tree of sorted runs in one flat array, O(n log n) build + space disclosed), and WaveletTree (the family's FIRST post-1.0 exotic: a STATIC wavelet MATRIX of level-wise flat bitvectors + a succinct O(1)-rank index that coordinate-compresses finite numbers to ranks, answering access / rank / select / quantile -- the k-th smallest value in an index range MergeSortTree deferred -- and rangeCount in worst-case O(log n), improving MergeSortTree's O(log^2 n) rangeCount, on the DEFAULT log2(n) axis; O(n log sigma) build + space disclosed), and CartesianTree (a STATIC, IMMUTABLE range-MINIMUM tree: a heap-ordered Cartesian tree built in O(n) whose rangeMinIndex / rangeMin answer the extreme's index / value over an index range in worst-case O(log n) via a binary-lifting LCA climb, with a materialized parent / left / right / depth topology you can walk -- the RMQ = LCA teaching bridge; O(n log n) lift table + space disclosed, on the DEFAULT log2(n) axis), and LinkCutTree (the family's FIRST dynamic-topology structure: a Sleator-Tarjan link-cut tree maintaining a FOREST of rooted trees under link / cut / evert with AMORTIZED O(log n) PATH aggregates -- min / max / sum / gcd, frozen at construction -- via a preferred-path splay decomposition, over a FIXED vertex set [0, capacity) where link / cut / evert flip EDGES only so no op allocates; because the folds are COMMUTATIVE, reversal (evert) is aggregate-invariant -- a lazy _rev bit, no mirrored aggregate; on the DEFAULT log2(n) axis), and EulerTourTree (the LinkCutTree sibling and the family's SUBTREE / dynamic-connectivity member: an UNROOTED forest over a FIXED vertex set [0, capacity) under link / cut answering connected, whole-COMPONENT folds, and SUBTREE folds -- v's side of edge (v, p) -- in EXPECTED O(log n) with ZERO allocation, via each tree's Euler tour held in a parent-pointer treap so the reads are NON-mutating; LCT folds PATHS, ETT folds SUBTREES and COMPONENTS -- the dynamic-forest pair) -- each zero-GC, each shipped with a log-linear Witness that fits nsPerOp = intercept + slope*log2(n) (or slope*(log2 n)^2 for Fenwick2D / SegmentTree2D / MergeSortTree) and shows the straight log line while an O(n) foil leaves it.

The O(log n) toolkit the ecosystem was missing

Almost no JavaScript data-structure library ships the evidence that its Big-O claim survives contact with a real engine -- megamorphic call sites, GC pauses, cache misses, deopts. lite-logn is a curated, tree-shakeable family of the O(log n) structures that actually matter, each zero-GC, each written to teach the trick that buys the logarithm, and each shipped with a harness that DEMONSTRATES the straight log line rather than asserting it. The complexity class IS the product.

lite-logn is the O(log n) sibling of @zakkster/lite-o1. lite-o1 proves a FLAT ops/ms line on a log-x axis (the constant -- slope ~ 0); lite-logn proves a STRAIGHT line on that same axis (one added level per doubling of n -- slope > 0, within a per-member band). The gate SHAPE differs; the discipline is identical: zero allocation on every hot path and a witness that turns "trust me, it is O(log n)" into a straight line you can see, with a foil that leaves it.

v1.5.0 ships twenty members: BinaryHeap, Fenwick, SegmentTree, SkipList, Treap, Scapegoat, MinMaxHeap, SplayTree, BinomialHeap, PairingHeap, FibonacciHeap, Fenwick2D, SegmentTree2D, SortedArray, PersistentSegTree, MergeSortTree, WaveletTree, CartesianTree, LinkCutTree and EulerTourTree. Members land one per session, each append-only so prior members stay byte-identical. The planned roster below fills in per release.

npm install @zakkster/lite-logn

import { Fenwick } from '@zakkster/lite-logn';

// A Fenwick tree (Binary Indexed Tree): point-update AND prefix-sum both O(log n).
const f = new Fenwick(1000);   // 1000 slots, all zero
f.update(10, 5);               // add 5 at index 10          -- O(log n)
f.update(20, 3);               // add 3 at index 20          -- O(log n)
f.prefix(15);        // -> 5   (sum of [0..15] inclusive)    -- O(log n)
f.rangeSum(10, 20);  // -> 8   (sum of [10..20] inclusive)   -- O(log n)
f.at(10);            // -> 5   (the single element at 10)    -- O(log n)
f.set(10, 100);      // set index 10 to 100 (absolute)       -- O(log n)
f.prefix(20);        // -> 103

// O(n) LINEAR bulk build (each cell adds itself to its parent in one pass):
const g = Fenwick.build([1, 2, 3, 4, 5]);
g.prefix(4);         // -> 15

Every hot op allocates zero bytes after construction, and npm run witness proves BOTH update and prefix hold the straight log line while their O(n) foils (a prefix-array rebuild and a naive re-sum) leave it.

Table of contents

• Why this exists
• What you get
• The roster
• The O(log n) Witness
• Benchmarks
• API reference
  • Constants
  • BinaryHeap
  • Fenwick
  • SegmentTree
  • SkipList
  • Treap
  • Scapegoat
  • MinMaxHeap
  • SplayTree
  • BinomialHeap
  • PairingHeap
  • FibonacciHeap
  • Fenwick2D
  • SegmentTree2D
  • SortedArray
  • PersistentSegTree
  • MergeSortTree
  • WaveletTree
  • CartesianTree
  • LinkCutTree
  • EulerTourTree
• Zero-GC design notes
• Testing
• What this is not
• Ecosystem
• License

Why this exists

A working programmer reaching for "keep the smallest element to hand" or "prefix sums that stay correct under updates" usually pays an O(n) cost hidden behind a friendly method name -- Array.prototype.shift, a full re-sum, a re-sort on every insert. The logarithm is the honest price of order, and it is cheap: one extra level of work per doubling of the data. But a naive O(log n) structure does new Node per insert, and that per-op allocation is a GC pause an engine will not honor -- it turns the clean logarithm into jitter.

lite-logn ships the O(log n) structures that matter with the allocation removed (array-embedded members are naturally node-free; pointer-based members use a pointer-free node pool) and the logarithm proven (the witness fits a straight log line and shows an O(n) foil leaving it). The complexity class is the product: you get the structure AND the evidence its bound is real on a real engine.

What you get

• Zero runtime dependencies. ESM only, ASCII-only source, one PascalCase main file (LogN.js), sideEffects: false.
• Zero allocation on every hot path. Proven by node --expose-gc test/torture.mjs (@zakkster/lite-leak + @zakkster/lite-gc-profiler): 0 B/op, gc major = 0, leak tracker size 0/0.
• A logarithm you can see. npm run witness fits nsPerOp = intercept + slope*log2(n) across a geometric n sweep, gates the R^2 floor + slope band, and shows an O(n) foil departing the line.
• Tree-shakeable named exports. Members share no mutable module state, so a bundler that imports one drops the others.
• Fail closed. Fixed, preallocated capacity; a typeof-guard at the door of every mutating op; null is not zero; an unknown option key is an error with a hint, never a silent ignore.

The roster

One member per session, each landing append-only (prior members stay byte-identical). At v1.5.0, twenty members -- BinaryHeap, Fenwick, SegmentTree, SkipList, Treap, Scapegoat, MinMaxHeap, SplayTree, BinomialHeap, PairingHeap, FibonacciHeap, Fenwick2D, SegmentTree2D, SortedArray, PersistentSegTree, MergeSortTree, WaveletTree, CartesianTree, LinkCutTree and EulerTourTree -- are shipped.

| Member | Version | Status | Shape | Hot ops | | --- | --- | --- | --- | --- | | BinaryHeap | 0.1.0 | shipped | array-embedded complete binary min|max heap over a flat Float64Array | push / pop O(log n), peek O(1) | | Fenwick (BIT) | 0.2.0 | shipped | flat Float64Array, lowest-set-bit walk (i & -i) | update / prefix / rangeSum / at / set O(log n) | | SegmentTree | 0.3.0 | shipped | single flat Float64Array(2n) (leaves n..2n-1); associative fold (min/max/sum/gcd) chosen at construction | query / update O(log n), at O(1) | | SkipList | 0.4.0 | shipped | pointer-free over a private free-list node pool; expected O(log n) | get / set / delete / successor / predecessor | | Treap | 0.5.0 | shipped | randomized-balanced augmented BST over the same node pool; expected O(log n) | get / has / set / delete / rank / select / successor / predecessor / forEach / rangeIter / split + merge | | Scapegoat | 0.6.0 | shipped | DETERMINISTIC weight-balanced augmented BST over the same node pool; worst-case O(log n) get, amortized O(log n) set/delete (zero-GC rebuild) | get / has / set / delete / rank / select / successor / predecessor / forEach / rangeIter (NO split/merge) | | MinMaxHeap | 0.7.0 | shipped | array-embedded double-ended PQ (DEPQ): one binary heap whose levels alternate min/max, two flat columns (_key/_id) | push / popMin / popMax O(log n), peekMin / peekMax / peekMinKey / peekMaxKey O(1) (non-addressable: NO changeKey/remove) | | SplayTree | 0.8.0 | shipped | self-adjusting BST ordered map: iterative top-down splay, four flat columns (_key/_value/_left/_right) over the shared free-list, NO balance metadata | get / has / set / delete / successor / predecessor amortized O(log n) (a read SPLAYS); LEAN (NO rank/select/split/merge) | | BinomialHeap | 0.9.0 | shipped | mergeable priority queue: a forest of binomial trees, six flat columns (_key/_id/_parent/_child/_sibling/_order) over a shared-arena free-list | push O(1) amortized, popMin O(log n), peekMin/peekMinKey O(1), meld O(log n) (consumes the arg); LEAN + non-addressable (NO decreaseKey/remove/rank/select) | | PairingHeap | 0.10.0 | shipped | ADDRESSABLE mergeable priority queue: a single multi-way tree (left-child/right-sibling), five flat columns (_key/_id/_child/_sibling/_parent) + arena-wide _pos reverse map + per-slot _owner + union-find _alias, over a shared-arena free-list | push/meld O(1), popMin/decreaseKey/remove amortized O(log n), peekMin/peekMinKey/has/keyOf O(1); ADDRESSABLE by arena-wide-unique id (NO rank/select/changeKey) | | FibonacciHeap | 0.11.0 | shipped | textbook-optimal ADDRESSABLE mergeable PQ: a lazy forest on CIRCULAR lists, eight flat columns (_key/_id/_left/_right/_child/_parent/_degree/_mark) + arena-wide _pos + _owner + _alias + a per-arena degree bucket, over a shared-arena free-list | push/meld/decreaseKey O(1) amortized (cascading cuts + mark bit), popMin/remove O(log n) amortized (degree consolidation), peekMin/peekMinKey/has/keyOf O(1); ADDRESSABLE by arena-wide-unique id (NO rank/select/changeKey); textbook-optimal but OFTEN slower wall-clock than Pairing/Binary | | Fenwick2D | 0.12.0 | shipped | 2D Binary Indexed Tree: a single flat Float64Array((rows+1)*(cols+1)), nested lowest-set-bit walk (i & -i on both dims), row 0 / col 0 the identity sentinels | update / prefix / rectSum / at / set O(log^2 n) = O(log rows * log cols); rows / cols O(1); SUM-ONLY + index-addressed (NO 2D min/max/gcd, NO changeKey/rank/select) | | SegmentTree2D | 0.13.0 | shipped | 2D segment tree of segment trees: a single flat Float64Array(4*rows*cols) (2R x 2C), associative fold (min/max/sum/gcd) chosen at construction; the general rectangle fold a 2D BIT cannot do | query / update O(log^2 n) = O(log rows * log cols); at O(1); rows / cols / kind O(1); index-addressed range FOLD (NO changeKey/rank/select, NO lazy range-update, commutative folds only) | | SortedArray | 0.14.0 | shipped | DYNAMIC read-optimized ordered map (key -> value) over two parallel SORTED Float64Array columns (_key ascending / _value); CONTIGUOUS storage, one shared lower-bound search | get / has / rank / successor / predecessor O(log n); select / keyAt / valueAt / min / max O(1); set / delete O(n) in-place copyWithin shift (0 B/op); the fastest forEach (a cache-friendly scan); unique keys (NO duplicate, NO changeKey) | | PersistentSegTree | 0.15.0 | shipped | FULLY PERSISTENT (branching) segment tree via PATH-COPYING: a persistent DAG of immutable nodes over three flat columns (_val Float64 / _left / _right Uint32) via a monotonic BUMP/APPEND allocator (NOT the free-list pool); associative fold (min/max/sum/gcd) chosen at construction | query / at O(log n) read-only; update(fromVersion, i, value) -> newVersion O(log n) (copies the root-to-leaf path, shares off-path subtrees, 0 B/op); every past version stays queryable + branchable; length / versions / versionCapacity / kind O(1); the family's FIRST persistent member (NO forEach/iterator -- a persistent DAG has no single live timeline) | | MergeSortTree | 0.16.0 | shipped | STATIC, IMMUTABLE offline range-RANK tree: a segment tree of SORTED runs packed by level into ONE flat Float64Array of n*(ceil(log2 n)+1) cells; source COPIED in at construction, NO mutators (the family's FIRST truly immutable member) | countLE(lo, hi, x) (how many values <= x in an index range) / rangeCount(lo, hi, vlo, vhi) (count in a value-window) worst-case O(log^2 n), 0 B/op read-only; length / size / cells O(1); PLAIN O(log^2 n) (no fractional cascading); kth-in-range deferred to a future WaveletTree; O(n log n) build + space disclosed (NO forEach/mutator -- static + immutable) | | WaveletTree | 1.1.0 | shipped | STATIC wavelet MATRIX: level-wise flat bitvectors (n*ceil(log2 distinct) bits) + per-level zero-count + a succinct O(1)-rank block index; coordinate-compresses finite numbers to distinct ranks at build; source COPIED in, immutable per query with NO per-element mutator -- the one exception is rebuildFrom, a whole-structure atomic rebuild in place | access(i) (value at index) / rank(value, i) (occurrences in prefix [0, i)) / select(value, k) (index of k-th occurrence) / quantile(lo, hi, k) (k-th smallest value in an index range -- the order statistic MergeSortTree deferred) / quantileInto(out, j, lo, hi, k) (0-box) / rangeCount(lo, hi, vlo, vhi) (value-window count) all worst-case O(log n), 0 B/op read-only; rebuildFrom(values) rebuilds in place; length / size / levels / distinct / bits O(1); DEFAULT log2(n) witness axis; rangeCount improves MergeSortTree's O(log^2 n) to O(log n); O(n log sigma) build + space disclosed (no per-element mutator / forEach) | | CartesianTree | 1.2.0 | shipped | STATIC, IMMUTABLE range-MINIMUM tree: a heap-ordered Cartesian tree built in O(n) (a monotonic-stack pass) + a flat n*(ceil(log2 n)+1) binary-lifting ancestor table; source COPIED in, kind (min/max) frozen at build, NO mutators | rangeMinIndex(lo, hi) (index of the extreme in an index range -- the gated op) / rangeMin(lo, hi) (its value) worst-case O(log n) via an LCA climb, 0 B/op; at(i) / parent(i) / left(i) / right(i) / depth(i) / root / length / size / kind O(1); DEFAULT log2(n) witness axis; RMQ = LCA the teaching bridge; O(n) build + O(n log n) lift + space disclosed (NO forEach/mutator -- static + immutable) | | LinkCutTree | 1.3.0 | shipped | the family's FIRST dynamic-topology structure: a Sleator-Tarjan link-cut tree -- a FOREST of rooted trees over a FIXED vertex set [0, capacity), preferred-path splay decomposition, eight flat columns, kind (min/max/sum/gcd) frozen at build; link / cut / evert flip EDGES only, NO per-op allocation / free-list / bump allocator | pathAggregate(u) (fold root -> u) / pathAggregate(u, v) (fold the u..v path inclusive -- the gated op) amortized O(log n), 0 B/op; link(child, parent) / cut(node) / evert(u) / setValue(id, value) amortized O(log n); findRoot(u) / connected(u, v) amortized O(log n) MUTATING reads; at(id) O(1) NON-mutating; clear() O(n); capacity / kind / edges getters O(1); DEFAULT log2(n) witness axis; AMORTIZED, MAX single-op disclosed not gated; PATH-only (subtree folds are the shipped EulerTourTree sibling's job, v1.5.0) | | EulerTourTree | 1.5.0 | shipped | the LinkCutTree sibling and the family's SUBTREE / dynamic-connectivity member: an UNROOTED forest over a FIXED vertex set [0, capacity) via a Henzinger-King Euler tour held in a parent-pointer TREAP; link / cut flip EDGES + arc indices only, NO per-op heap allocation; reads are NON-mutating (expected O(log n), the SkipList / Treap randomized class) | subtreeAggregate(v, p) (fold v's side of edge (v, p) -- the gated op) / componentAggregate(v) expected O(log n); link(u, v) / cut(u, v) / setValue(v, x) expected O(log n); connected(u, v) / componentSize(v) / subtreeSize(v, p) / hasEdge(u, v) expected O(log n) NON-mutating; at(v) O(1); clear() O(n); capacity / kind / edges getters O(1); DEFAULT log2(n) witness axis; EXPECTED, MAX single link / cut disclosed not gated; NO path fold, NO evert (LinkCutTree's job). LCT or ETT? Path fold / evert -> LinkCutTree; subtree or component fold, read-only connectivity -> EulerTourTree |

Later tiers (OrderStatTree, IndexedHeap, and presets) are queued in ROADMAP.md.

The O(log n) Witness

The family anchor. Time a fixed batch of the hot op at each n in a geometric sweep, fit nsPerOp = intercept + slope * log2(n) by least squares, and gate:

• R^2 >= floor (a straight line fits -- genuinely logarithmic), AND
• slope inside the member's band (the per-level cost, ns/level), AND
• the FOIL leaves the line (low R^2 -- the O(n) default a working programmer reaches for, shown losing as n grows).

For amortized / randomized members the witness also prints the MAX single-op time -- the honesty hook: a rebuild spike or a degenerate tail shows as a tall bar even when the mean still fits the line. The R^2 floor (0.958) is frozen family-wide in BinaryHeap; each member then calibrates its OWN per-op slope band (median-of-15 fit-runs x [0.6, 1.4]), because a cheaper op honestly has a lower per-level slope (see decisions/0004-witness-band.md). As of v1.5.0 the witness gates twenty-five ops (five bands -- SegmentTree update, SegmentTree2D update, PersistentSegTree query, Fenwick prefix, Fenwick2D update -- re-centered from their 1.3.0 values after F4 / the iterative _query removed a per-level HeapNumber box, so those ops are legitimately faster; see decisions/0004-witness-band.md): BinaryHeap pop (R^2 ~ 0.99, slope ~ 8-10 ns/level), Fenwick update (R^2 ~ 0.98-0.99, slope ~ 2.9-3.0 ns/level) and prefix (R^2 ~ 0.99, slope ~ 0.88 ns/level, band [0.53, 1.23], re-centered 1.4.0), SegmentTree update (R^2 ~ 0.98, slope ~ 0.72 ns/level, band [0.43, 1.00]) and query (R^2 ~ 0.99, slope ~ 7 ns/level, band [4.30, 10.04]), SkipList get (R^2 ~ 0.97-0.99, slope ~ 9 ns/level, band [5.27, 12.30]) and set (R^2 ~ 0.97-0.99, slope ~ 14 ns/level, band [8.36, 19.50]), Treap get (R^2 ~ 0.99, slope ~ 4 ns/level, band [2.55, 5.95]), Scapegoat get (R^2 ~ 0.99, slope ~ 4 ns/level, band [2.41, 5.63]), MinMaxHeap popMin (R^2 ~ 0.99, slope ~ 10.3 ns/level, band [6.18, 14.42]), SplayTree get (R^2 ~ 0.98, slope ~ 27 ns/level, band [16.39, 38.24], sweep [2^12, 2^17]), BinomialHeap popMin (R^2 ~ 0.98, slope ~ 44.8 ns/level, band [26.89, 62.75], sweep [2^11, 2^17]), PairingHeap popMin (R^2 ~ 0.99 median-of-5 fits, slope ~ 21.4 ns/level, band [13.08, 30.52], sweep [2^11, 2^17]), FibonacciHeap popMin (R^2 ~ 0.98 median-of-7 fits, slope ~ 45 ns/level, band [27.18, 63.41], sweep [2^11, 2^17]), and -- on the family's FIRST squared-log axis (nsPerOp = intercept + slope*(log2 n)^2) -- Fenwick2D update (R^2 ~ 0.998 median-of-7 fits, slope ~ 3.3 ns/level^2, band [1.19, 4.62], bimodal -- see 0004, square sides [2^5, 2^11]) and rectSum (R^2 ~ 0.9998, slope ~ 4.4 ns/level^2, band [2.90, 6.77]), and -- the SECOND member on that squared-log axis -- SegmentTree2D update (R^2 ~ 0.99, slope ~ 2.55 ns/level^2, band [1.53, 3.57], square sides [2^5, 2^11]) and query (R^2 ~ 0.9999, slope ~ 5.8 ns/level^2, band [3.06, 7.15]; both single-fit, rock-steady, no median-of-fits needed), and -- back on the DEFAULT log2(n) axis -- SortedArray get (R^2 ~ 0.98 median-of-7 fits, slope ~ 1.0 ns/level, band [0.59, 1.38], sweep [2^12, 2^18]), and -- also on the DEFAULT log2(n) axis -- PersistentSegTree query (R^2 ~ 0.98, slope ~ 15.9 ns/level, band [9.53, 22.23], sweep [2^11, 2^17]), and -- the family's THIRD member on the squared-log axis (nsPerOp = intercept + slope*(log2 n)^2) -- MergeSortTree countLE (R^2 ~ 0.97 median-of-7 fits, slope ~ 5.2 ns/level^2, band [3.13, 7.31], sweep [2^13, 2^18]), and -- back on the DEFAULT log2(n) axis, the family's FIRST post-1.0 exotic -- WaveletTree quantile (R^2 ~ 0.97 median-of-7 fits, slope ~ 15.2 ns/level, band [9.15, 21.35], sweep [2^12, 2^18]), and -- also on the DEFAULT log2(n) axis -- CartesianTree rangeMinIndex (R^2 ~ 0.98 median-of-7 fits, slope ~ 2.8 ns/level, band [1.69, 3.93], sweep [2^12, 2^18]), and -- also on the DEFAULT log2(n) axis, the family's FIRST DYNAMIC-topology and FIRST amortized-dynamic member -- LinkCutTree pathAggregate (R^2 ~ 0.99 median-of-7 fits, slope ~ 56 ns/level, band [33.74, 78.74], sweep [2^12, 2^18]), and -- its EXPECTED-time sibling -- EulerTourTree subtreeAggregate (R^2 ~ 0.98-0.99 median-of-9 fits, slope ~ 92 ns/level, band [55.16, 128.71], sweep [2^9, 2^17], MAX single link / cut disclosed) all ON the line. PersistentSegTree is the family's FIRST persistent / branching member: its query is a WORST-CASE O(log n) read-only descent over a version's root (independent of which version is read -- all versions share the same height), so it fits the default single-log axis; because a persistent path-copying query chases scattered bump-allocated slots across the node arena, its per-level slope sits with the pointer-chasing members and its post-torture run has genuine scheduler / thermal residue, so this lane opts into the MEDIAN of 7 independent sweep-fits as measurement-quality insurance (the frozen 0.958 floor and slope band are untouched). Its O(n) linear-scan foil leaves the line. WORST-CASE member: no max-single-op line. MergeSortTree is the family's FIRST truly IMMUTABLE member and its offline range-RANK structure: its countLE is a WORST-CASE O(log^2 n) descent of the O(log n) canonical nodes covering the index range, each binary-searching that node's sorted run, so it fits the SAME squared-log axis Fenwick2D / SegmentTree2D use; because it chases scattered node runs across a large flat table, a single sweep-fit's R^2 can dip below the floor in a minority of runs, so this lane opts into the MEDIAN of 7 independent sweep-fits (the frozen 0.958 floor + slope band are untouched). Its O(n) linear-scan-count foil is exponential on the squared-log axis and leaves the line. STATIC + WORST-CASE (build-once immutable, no randomization / amortization): no max-single-op line. WaveletTree is the family's FIRST post-1.0 exotic and its wavelet MATRIX: its quantile is a WORST-CASE O(log sigma) SINGLE descent of the ceil(log2 distinct) levels with O(1) succinct-rank work per level, so unlike MergeSortTree's per-node binary search it fits the DEFAULT single-log axis (nsPerOp = intercept + slope*log2(n)); because a quantile descent reads TWO succinct ranks per level across the level-packed bitvectors + rank index, a single sweep-fit's R^2 can dip below the floor in a minority of post-torture runs, so this lane opts into the MEDIAN of 7 independent sweep-fits (the frozen 0.958 floor + slope band are untouched). Its O(n log n) linear-kth foil (copy the window, sort, index k) leaves the line. STATIC + WORST-CASE (build-once immutable, no randomization / amortization): no max-single-op line. CartesianTree is the family's range-MINIMUM tree and its binding of the RMQ = LCA bridge: its rangeMinIndex is a WORST-CASE O(log n) binary-lifting LCA climb (depth-equalize lo and hi, then co-lift in lock-step over the flat ancestor table), so it fits the DEFAULT single-log axis (nsPerOp = intercept + slope*log2(n)) with the family's SHALLOWEST-but-one per-level slope (each jump is a single _up array read, no per-op value compare -- kind is baked into the tree); because the climb reads scattered ancestor cells and its post-torture run carries scheduler / thermal residue, this lane opts into the MEDIAN of 7 independent sweep-fits (the frozen 0.958 floor + slope band are untouched). Its O(n) linear extreme-scan foil leaves the line. STATIC + WORST-CASE (build-once immutable, no randomization / amortization): no max-single-op line. LinkCutTree is the family's FIRST dynamic-topology member and its binding of the preferred-path splay decomposition: its pathAggregate is an AMORTIZED O(log n) single splay descent that folds a root-to-node (or evert-then-access two-endpoint) path over the preferred-path splay forest -- each preferred path a splay tree keyed by depth, path-parent pointers stitching the paths -- so it fits the DEFAULT single-log axis (nsPerOp = intercept + slope*log2(n)); because a single access can splay + expose a deep chain, the witness prints the MAX single pathAggregate as a disclosure, never gated (the SplayTree / PairingHeap / FibonacciHeap amortized precedent). It is measured over a UNIFORM-RANDOM working set of size n (a shuffled permutation of all n vertices, cycled -- SplayTree.get's discipline) so every op re-prefers a fresh path and the amortized line shows; its per-level slope band was calibrated on a warm post-torture median (~56 ns/level, band [33.74, 78.74]), the state npm run verify runs in. Because the folds (min / max / sum / gcd) are COMMUTATIVE, reversal (evert) is aggregate-invariant -- it swaps children and flips a lazy _rev bit, no mirrored aggregate is kept. This lane opts into the MEDIAN of 7 independent sweep-fits (the frozen 0.958 floor + slope band are untouched). Its O(depth) naive parent-walk foil is O(n) on a deep chain and leaves the line. SortedArray is the family's READ-OPTIMIZED ordered map: its get is a WORST-CASE O(log n) contiguous lower-bound binary search (the deterministic Scapegoat.get analogue, no RNG), the family's SHALLOWEST per-level slope because a contiguous search touches fewer cache lines per level than a pointer-chasing BST descent -- so this being the fastest lane, its ~6 ns fit span needs the widest + highest n-sweep and a 1e6-iteration measurement to keep per-point noise off the fit; the median-of-7 fit is measurement-quality insurance against the scheduler/thermal residue of the post-torture run (the frozen 0.958 floor and slope band are untouched). Because a genuine insert is an O(n) tail shift, the witness also prints the MAX single insert as a disclosure, never gated. FibonacciHeap is the mergeable arc's FINALE -- the textbook-optimal ADDRESSABLE heap: push/meld/decreaseKey are O(1) AMORTIZED (a cascading cut governed by a per-node mark bit) and popMin/remove are O(log n) AMORTIZED (a degree consolidation), and because a single popMin can do an O(n) consolidation and a single decreaseKey an O(n) cascade the witness prints BOTH the MAX single popMin AND the MAX single decreaseKey as disclosures, never gated. It carries the FAMILY's STEEPEST per-level slope (a lazy forest consolidated on demand -- the largest constant factors of any heap here); honestly, it is textbook-optimal in asymptotics but OFTEN slower wall-clock than Pairing/Binary on real hardware. Its full-drain average has even more run-to-run SHAPE variance than the pairing two-pass, so a single sweep-fit's R^2 is flaky (~0.981-0.988, and can dip below the floor across meta-runs); this lane gates on the MEDIAN of 7 independent sweep-fits -- measurement-quality only, the frozen 0.958 floor and slope band are untouched, and no unreproducible "every run" is claimed. PairingHeap is the mergeable arc's ADDRESSABLE heap: its popMin is AMORTIZED O(log n) (a TWO-PASS combine of the root's child list -- pointer-free, 0 B/op), and because a single pop can fold a long child list the witness prints the MAX single popMin as a disclosure, never gated; its per-level slope sits between the array-embedded heaps and BinomialHeap (a single multi-way tree, not a forest). A pairing-heap full-drain average has genuine run-to-run SHAPE variance, so a single sweep-fit's R^2 is flaky (~0.945-0.985, dipping below the floor in a minority of runs); this lane gates on the MEDIAN of 5 independent sweep-fits (rejecting the occasional tilted sweep) -- measurement-quality only, the frozen 0.958 floor and slope band are untouched. BinomialHeap is the family's first MERGEABLE heap: its popMin is WORST-case O(log n) (unlink the extreme root, reverse its child list, union back, rescan the roots -- no max-single-op line), and its per-level slope sits well above the array-embedded heaps because it chases scattered forest slots (which is why it is gated over the cache-resident exact-power window, not the [1e4, 1e6] band). SplayTree is DETERMINISTIC and SELF-ADJUSTING: its get is AMORTIZED O(log n) (a read SPLAYS the touched key to the root -- the slope sits well above a read-only BST descent because rotations rewrite links every op), measured over a uniform-random working set of size n so the amortized line shows (a skewed pattern would flatten it -- the member's speedup, not what a straight-log witness measures); because a single cold access can splay an O(n) chain, the witness also prints the MAX single get as a disclosure, never gated. Scapegoat is DETERMINISTIC, so its get is WORST-case (not expected) O(log n); its rebuild spike lives on the AMORTIZED set path and is proven not by a per-op line but by an amortized-trace assertion -- the cumulative ascending-insert (rebuild-heavy) cost/op tracks a LOG curve (last/first ratio ~1.5x over [2^11, 2^17], gated < 4x) where a rebuild-less BST would degenerate to an O(n)-amortized chain and blow the ratio to ~64x. Treap's descent touches one node per level, so its per-level slope is lower than SkipList's tower search -- expected, which is why only the R^2 floor is shared and each op calibrates its own band. SkipList's two ops are gated over DIFFERENT sweeps -- each measured where its logarithm is visible, not where the cache wall is: get (a clean search with no per-op randomness) over [2^11, 2^17] for dynamic range; set (a heavier insert+delete churn whose per-insert tower height is random) over the smaller, fully cache-resident [2^9, 2^14] so the fit sees the structural level count, not DRAM latency. Because SkipList is EXPECTED (not worst-case) O(log n), the witness also prints the MAX single insert over a realistic randomized build trace -- the unlucky-tower tail a mean hides. Each op's O(n) foil fits well below the floor: the sorted-array insert (BinaryHeap / SkipList) foil runs R^2 ~ 0.77-0.87, the Fenwick foils (prefix-array rebuild, naive re-sum) and SkipList's linear-scan search foil hold at R^2 ~ 0.75-0.82, and SegmentTree's foils (whole-tree rebuild per update, scan-fold per query) fit at R^2 ~ 0.72-0.85 -- all foil families sit comfortably under the 0.958 floor.

Benchmarks

A repo-only, eight-dimension benchmark suite (benchmark/, ADOPTED field-for-field from @zakkster/lite-o1's "Bench v2") surrounds the witness anchor. It is dev infra: NOT in the published tarball, imports NOTHING from the package but LogN.js, and spawns one child process per (member x dimension) cell for a clean GC/JIT state. D1 is the O(log n) Witness itself -- it DELEGATES to the shipped test/witness.mjs (the same frozen kernels, per-op sweeps, R^2 floor and slope bands), so the headline dimension never re-implements the fit. Run it yourself:

npm run bench            # 128 cells -> benchmark/results.json + summary tables
npm run bench:report     # the above, then benchmark/report.html (hand-rolled inline-SVG graphs)

Numbers below are one run on an Apple M4 Pro (arm64), Node v26 -- machine-specific, reproducible from a fixed seed (0x9e3779b1). Every applicable cell is a positive number; every inapplicable cell is the string n/a (never a numeric 0).

D1 -- the O(log n) Witness fit (per gated op-row)

Each op fits nsPerOp = intercept + slope*log2(n). ON-LINE = R^2 >= 0.958 (the frozen family floor) AND slope inside the member's per-op band; the O(n) foil MUST leave the line (foil R^2 < 0.958). All twenty-five op-rows sit ON the line; all twenty-five foils leave it.

| op-row | R^2 | slope (ns/level) | slope band | on line? | foil | foil R^2 | foil off? | | --- | --- | --- | --- | --- | --- | --- | --- | | BinaryHeap.pop | 0.996 | 8.4 | [5.76, 13.44] | ON | sorted-array insert | 0.83 | off | | Fenwick.update | 0.980 | 2.8 | [1.84, 4.30] | ON | prefix-array rebuild | 0.76 | off | | Fenwick.prefix | 0.99 (median-of-9 fits) | 0.88 | [0.53, 1.23] | ON | naive re-sum | 0.75 | off | | SegmentTree.update | 0.98 | 0.72 | [0.43, 1.00] | ON | whole-tree rebuild | 0.82 | off | | SegmentTree.query | 0.998 | 7.0 | [4.30, 10.04] | ON | scan-fold | 0.73 | off | | SkipList.get | 0.988 | 8.0 | [5.27, 12.30] | ON | linear scan | 0.79 | off | | SkipList.set | 0.985 | 12.1 | [8.36, 19.50] | ON | sorted-array insert | 0.77 | off | | Treap.get | 0.988 | 4.0 | [2.55, 5.95] | ON | linear scan | 0.79 | off | | Scapegoat.get | 0.988 | 3.8 | [2.41, 5.63] | ON | linear scan | 0.79 | off | | MinMaxHeap.popMin | 0.99 | 10.3 | [6.18, 14.42] | ON | linear min-scan-and-splice | 0.77 | off | | SplayTree.get | 0.98 | 27.3 | [16.39, 38.24] | ON | linear scan | 0.80 | off | | BinomialHeap.popMin | 0.98 | 44.8 | [26.89, 62.75] | ON | linear min-scan-and-splice | 0.77 | off | | PairingHeap.popMin | 0.99 (median-of-5 fits) | 21.4 | [13.08, 30.52] | ON | linear min-scan-and-splice | 0.79 | off | | FibonacciHeap.popMin | 0.98 (median-of-7 fits) | 45.3 | [27.18, 63.41] | ON | linear min-scan-and-splice | 0.90 | off | | Fenwick2D.update | 0.99 (median-of-fits) | 3.3 (bimodal ~2.0 / ~3.3) | [1.19, 4.62] | ON | dense rectangle rescan | 0.80 | off | | Fenwick2D.rectSum | 0.99 | 4.8 | [2.90, 6.77] | ON | dense rectangle rescan | 0.80 | off | | SegmentTree2D.update | 0.99 | 2.55 | [1.53, 3.57] | ON | 2D grid rebuild | 0.80 | off | | SegmentTree2D.query | 0.9999 | 5.8 | [3.06, 7.15] | ON | dense rectangle rescan | 0.80 | off | | SortedArray.get | 0.98 (median-of-7 fits) | 1.0 | [0.59, 1.38] | ON | linear scan | 0.78 | off | | PersistentSegTree.query | 0.98 | 15.9 | [9.53, 22.23] | ON | scan-fold | 0.70 | off | | MergeSortTree.countLE | 0.97 (median-of-7 fits) | 6.8 | [3.13, 7.31] | ON | linear scan-count | 0.86 | off | | WaveletTree.quantile | 0.97 (median-of-7 fits) | 15.2 | [9.15, 21.35] | ON | linear-kth (sort window) | 0.85 | off | | CartesianTree.rangeMinIndex | 0.98 (median-of-7 fits) | 2.8 | [1.69, 3.93] | ON | linear extreme-scan (O(n)) | 0.80 | off | | LinkCutTree.pathAggregate | 0.99 (median-of-7 fits) | 56 | [33.74, 78.74] | ON | naive parent-walk (O(depth)/O(n)) | 0.80 | off | | EulerTourTree.subtreeAggregate | 0.98-0.99 (median-of-9 fits) | 92 | [55.16, 128.71] | ON | adjacency DFS (O(component)/O(n)) | 0.79 | off |

Fenwick2D squared-log axis (the family's FIRST). Fenwick2D's ops are O(log^2 n), not O(log n), so its two witness lanes fit nsPerOp = intercept + slope*(log2 n)^2 -- the slope column above for Fenwick2D.update / Fenwick2D.rectSum is therefore ns per (log2 n)^2 UNIT (not per level), gated over exact power-of-two square sides 2^5..2^11. The per-lane xOf axis hook that makes this possible defaults to Math.log2, so every prior lane's fit is byte-identical. Each O(n^2)-per-op foil (a dense rectangle rescan) leaves the squared-log line. Fenwick2D is WORST-case (no MAX-single-op disclosure).

Scapegoat amortized-trace (the rebuild honesty). Scapegoat's get is WORST-case O(log n) (a deterministic weight-balance height bound), so it carries no expected-op MAX-single-op disclosure. The rebuild spike lives on the AMORTIZED set path; D1 proves the amortization not with a per-op line but with an amortized-trace assertion -- the cumulative ascending-insert (rebuild-heavy) cost/op tracks a LOG curve (last/first ratio ~1.5x over [2^11, 2^17], gated < 4x) where a rebuild-less BST would blow to ~64x.

SkipList counter-foil (the order tax). A native Map is O(1) at get/set (~27 ns/op, FLATTER than any log line) but ORDER-BLIND: it cannot answer successor / predecessor / rangeIter. The log factor SkipList pays buys exactly the ordered queries Map cannot. SkipList is EXPECTED O(log n), so D1 also DISCLOSES its MAX single insert (an unlucky tall tower over a randomized build: ~18-130 us, not gated).

D3 -- memory (bytes / live vs a theoretical floor)

| member | peak bytes @ 64Ki | B/live | theo min | overhead x | note | | --- | --- | --- | --- | --- | --- | | BinaryHeap | 1,048,576 | 16.0 | 12 | 1.33 | key (8) + id (4) dense; _pos reverse map is the universe overhead | | Fenwick | 524,296 | 8.0 | 8 | 1.00 | one Float64 tree cell per element -- exact | | SegmentTree | 1,048,576 | 16.0 | 16 | 1.00 | the 2n array -- exact | | SkipList | 5,767,320 | 88.0 | 16 | 5.50 | key + value dense; the ceil(log2 cap)+1 link columns are the tower overhead | | Treap | 2,359,328 | 36.0 | 16 | 2.25 | key + value + priority + child/parent + subtree-size per node | | Scapegoat | 2,621,472 | 40.0 | 16 | 2.50 | key + value + child links + subtree-size counters per node | | MinMaxHeap | 786,432 | 12.0 | 12 | 1.00 | key (8) + id (4) dense, no reverse map -- exact | | SplayTree | 1,835,032 | 28.0 | 16 | 1.75 | key + value + child/parent pointers per node | | BinomialHeap | 2,097,180 | 32.0 | 12 | 2.67 | key + child/sibling/parent forest pointers per node | | PairingHeap | 2,359,324 | 36.0 | 12 | 3.00 | key + child/sibling/prev pointers per node | | FibonacciHeap | 2,949,261 | 45.0 | 12 | 3.75 | key + child/sibling/parent + degree/mark per node -- the steepest store | | Fenwick2D | 528,392 | 8.1 | 8 | 1.01 | one Float64 cell per grid element -- near-exact | | SegmentTree2D | 2,097,152 | 32.0 | 32 | 1.00 | the 2n x 2n grid -- exact | | SortedArray | 1,048,576 | 16.0 | 16 | 1.00 | key + value dense contiguous -- exact | | PersistentSegTree | 2,114,820 | 32.3 | 32 | 1.01 | path-copied node arena; ~1% slot slack over the node size | | MergeSortTree | 8,912,896 | 136.0 | 8 | 17.00 | a sorted run copied at each of log n levels -- the offline range-rank space cost | | WaveletTree | 688,256 | 10.5 | 8 | 1.31 | COMPUTED (not measured): n*levels bits + ~1.25x rank index + 8*sigma remap; B/live ~ 1.25*levels/8 + 8*sigma/n (distinct corpus sigma=n, levels=16 @ 64Ki) -- the remap dominates | | CartesianTree | 6,029,312 | 92.0 | 8 | 11.50 | COMPUTED (not measured): val(8) + left/right/parent/depth (4x4) + the n x (ceil(log2 n)+1) Int32 binary-lifting ancestor table (4*L, L=17 @ 64Ki); the ancestor table dominates | | LinkCutTree | 2,162,721 | 33.0 | 8 | 4.13 | COMPUTED (not measured): eight flat columns per vertex -- _val+_agg (F64, 16) + _l/_r/_p (U32, 12) + _rev (U8, 1) + _stk (U32, 4) | | EulerTourTree | 12,320,716 | 188.0 | 8 | 23.50 | 3V-1 node slots x (6 U32 + 2 F64) + _stk + a pow2 (>= 4V) arc table (2 Int32 + 1 U32) + the arc free-list -- the subtree-fold + connectivity space cost (~188-236 B/vertex) |

The overhead-x load-factor curve RISES as load falls for the heap + pointer-node members (BinaryHeap, SkipList, Treap, Scapegoat, MinMaxHeap, SplayTree, BinomialHeap, PairingHeap, FibonacciHeap, SortedArray -- fixed backing over fewer live) and is FLAT for the INDEX-ADDRESSED members (Fenwick, SegmentTree, Fenwick2D, SegmentTree2D, PersistentSegTree, MergeSortTree, and the vertex-addressed LinkCutTree + EulerTourTree -- every cell / vertex is always live) -- another honest n/a where insertion order does not apply. MergeSortTree's 17x is the family's highest, the disclosed space co-headline of an offline range-rank structure.

D5 -- bundle size + tree-shaking (esbuild min + gzip)

A single-member import must be < 40% of the all-member import. All twenty clear it comfortably against the full twenty-member bundle (23,948 B gzip): the heaviest lone members (EulerTourTree at 0.134, FibonacciHeap at 0.122) stay well under the floor, the lightest (MergeSortTree) is 0.046, and every single-member import is far below 0.40. Every single-member import drops the vast majority of the code.

| member | single gz (B) | all gz (B) | ratio | < 40%? | | --- | --- | --- | --- | --- | | BinaryHeap | 1,580 | 23,948 | 0.066 | yes | | Fenwick | 1,565 | 23,948 | 0.065 | yes | | SegmentTree | 1,491 | 23,948 | 0.062 | yes | | SkipList | 1,574 | 23,948 | 0.066 | yes | | Treap | 2,149 | 23,948 | 0.090 | yes | | Scapegoat | 1,939 | 23,948 | 0.081 | yes | | MinMaxHeap | 1,378 | 23,948 | 0.058 | yes | | SplayTree | 1,481 | 23,948 | 0.062 | yes | | BinomialHeap | 1,979 | 23,948 | 0.083 | yes | | PairingHeap | 2,486 | 23,948 | 0.104 | yes | | FibonacciHeap | 2,910 | 23,948 | 0.122 | yes | | Fenwick2D | 1,659 | 23,948 | 0.069 | yes | | SegmentTree2D | 1,898 | 23,948 | 0.079 | yes | | SortedArray | 1,293 | 23,948 | 0.054 | yes | | PersistentSegTree | 1,944 | 23,948 | 0.081 | yes | | MergeSortTree | 1,101 | 23,948 | 0.046 | yes | | WaveletTree | 2,732 | 23,948 | 0.114 | yes | | CartesianTree | 1,177 | 23,948 | 0.049 | yes | | LinkCutTree | 1,631 | 23,948 | 0.068 | yes | | EulerTourTree | 3,209 | 23,948 | 0.134 | yes |

D6 -- GC pressure (the 0 B/op gate as a curve, per op-row)

All twenty-five gated op-rows report 0 B/op across the n = 1e3..1e6 sweep, with max major GC = 0. The precise proof stays node --expose-gc test/torture.mjs (via @zakkster/lite-gc-profiler); D6 is the portable curve (min heap-delta over independent passes -- heap-accounting jitter only ADDS, so a truly-zero kernel hits 0 on its best pass while a per-op allocator stays positive on every pass).

The other dimensions

• D2 amortized cost -- cumulative ns/op stays bounded over a ~1M-op mixed trace (drift < 1.0 here: the trace speeds up as the JIT warms, never degrades).
• D4 cache (PROXY, labelled) -- dense forEach iteration vs random single-element lookup; the random/dense gap is ~1.9x (SegmentTree) to ~2.9x (SkipList). No native perf counters.
• D7 scalability -- numeric substrates: string + object keys read n/a on all twenty. Load factors 0.3/0.5/0.7/0.9; insertion order (sorted / random / adversarial-reverse) applies to the comparison-ordered BinaryHeap + SkipList + Treap + Scapegoat + MinMaxHeap + SplayTree + BinomialHeap + PairingHeap + FibonacciHeap, and reads n/a for the index-addressed Fenwick + SegmentTree + Fenwick2D + SegmentTree2D + PersistentSegTree + MergeSortTree + WaveletTree + CartesianTree + LinkCutTree + EulerTourTree (vertex-id-addressed) and for the shift-insert SortedArray.
• D8 workloads -- churn (all twenty members) + an ordered scan (successor + rangeIter, on the ordered maps SkipList + Treap + Scapegoat + SplayTree + SortedArray; n/a elsewhere -- the heaps BinaryHeap / MinMaxHeap / BinomialHeap / PairingHeap / FibonacciHeap are priority queues, and Fenwick / SegmentTree / Fenwick2D / SegmentTree2D / PersistentSegTree / MergeSortTree / WaveletTree / CartesianTree / LinkCutTree / EulerTourTree are index-addressed / positional -- not ordered maps).

Disclosures (floating-point + worst-case honesty)

• Fenwick / Fenwick2D cancellation. The sum-kind structures hold a value spread across a logarithmic set of cells; a query subtracts prefixes. After a very large overwrite (e.g. set(i, 1e15) then set(i, small)), a different small element can read slightly wrong (the large magnitude swamped the shared cells' mantissa) UNTIL the large value is cleared from its cells -- a one-time rounding artefact of the overwrite, NOT accumulating drift. A churn test measured the drift at ~1.1e-12 over 1e7 overwrites: it does not grow with op count. The S1 magnitude budget bounds this so no intermediate can reach Infinity.
• Signed zero in the ordered maps. -0 and +0 are the SAME key: a set under one sign then the other MERGES into one entry and the FIRST-written sign wins the stored key (reads of keyAt / successor return that sign). WaveletTree normalizes -0 to +0 at build (S4); the ordered maps (SkipList / Treap / Scapegoat / SplayTree / SortedArray) only disclose it.
• Worst single-op times (amortized / self-adjusting members, n=131k, this machine). The witness gates the FITTED line but also prints the MAX single op as honesty: FibonacciHeap popMin ~2.36 ms, PairingHeap popMin ~1.59 ms, LinkCutTree findRoot ~1.26 ms, Scapegoat set (rebuild spike) ~783 us, SplayTree get (cold deep splay) ~647 us. These are the amortized tail a mean hides; they are disclosed, never gated.

API reference

Constants

| Export | Type | Value | Meaning | | --- | --- | --- | --- | | VERSION | string | '1.5.2' | The package version. One of the three version sites (package.json / LogN.js VERSION const / llms.txt), kept in lockstep and enforced in review. |

BinaryHeap

An indexed binary heap (an addressable priority queue): a min|max binary heap over three parallel, pointer-free typed arrays -- _key (Float64Array, the priority at each heap slot), _id (Uint32Array, the entity id at each slot), and _pos (Int32Array, the reverse map entity-id -> slot, sentinel -1 == absent). A plain binary heap gives O(log n) push / pop but cannot find an arbitrary element to reprioritize; the reverse-index map buys O(log n) changeKey / remove by a caller-supplied entity id. Children of slot i are 2i+1 / 2i+2. Entity ids are integers in [0, capacity); keys are finite numbers. Every hot op allocates zero bytes after construction (hole-punching sift -- one write per level, no 3-write swap).

import { BinaryHeap } from '@zakkster/lite-logn';

const pq = new BinaryHeap(1024, 'min');   // capacity 1024, min-heap
pq.push(7, 5.0);                          // entity 7 at priority 5.0
pq.push(3, 2.5);
pq.push(9, 8.0);
pq.peek();        // -> 3   (id of the extremum)
pq.topKey();      // -> 2.5 (its key)
pq.changeKey(9, 1.0);   // reprioritize entity 9 to the front
pq.pop();         // -> 9   (removes and returns the new extremum)
pq.remove(7);     // -> true (addressable delete by id)

// Floyd O(n) bulk build from parallel arrays:
const heap = BinaryHeap.build('max', [0, 1, 2, 3], [4.0, 1.0, 9.0, 2.0], 16);
heap.pop();       // -> 2   (the id whose key 9.0 is the max)

| Member | Signature | Complexity | Notes | | --- | --- | --- | --- | | constructor | new BinaryHeap(capacity, kind = 'min') | O(capacity) | capacity integer in [1, 2^31-1]; kind is 'min' or 'max'. Allocates the three typed arrays once; _pos.fill(-1). | | push | push(id, key) -> void | O(log n) | id in [0, capacity), not already present; key finite. Throws on out-of-range/duplicate id, non-finite key, or full heap. | | pop | pop() -> number \| undefined | O(log n) | Removes and returns the extremum's id; undefined if empty (no throw). | | peek | peek() -> number \| undefined | O(1) | The extremum's id; undefined if empty. | | topKey | topKey() -> number \| undefined | O(1) | The extremum's key; undefined if empty. | | keyOf | keyOf(id) -> number \| undefined | O(1) | The key associated with id; undefined if absent. Out-of-range id throws. | | has | has(id) -> boolean | O(1) | True iff id is resident. Out-of-range id throws. | | changeKey | changeKey(id, newKey) -> void | O(log n) | Reprioritize a present entity (auto-direction sift); a non-member id throws. | | remove | remove(id) -> boolean | O(log n) | Idempotent: false if absent, true if removed. | | clear | clear() -> void | O(capacity) | Resets size and the reverse map. | | forEach | forEach(fn) -> void | O(n) | Visits (id, key) in UNSPECIFIED (heap-array) order -- NOT sorted / pop order. | | [Symbol.iterator] | for (const id of heap) | O(n) | Yields live ids in UNSPECIFIED order. | | size / capacity / kind | getters | O(1) | Live count / fixed capacity / 'min' | 'max'. | | BinaryHeap.build | build(kind, ids, keys, capacity) -> BinaryHeap | O(n) | Floyd bulk build from parallel arrays; fails closed on duplicate/out-of-range id, non-finite key, or count > capacity. |

Fenwick

A Fenwick tree (Binary Indexed Tree): BOTH point-update AND prefix-sum in O(log n) over a single flat Float64Array, using nothing but the lowest-set-bit walk (i & -i). It answers the most delightfully non-obvious complexity question in the family -- "how can update AND query both be logarithmic on a plain array?" -- and the witness proves it with TWO straight log lines. Public indices are 0-based in [0, length); internally the tree is 1-based, so _t[0] is the unused identity sentinel and is never read as data (null is not zero). update climbs by i & -i (one _t touch per level); prefix descends by i & -i (one read per level); rangeSum and at are pairs of inlined prefix walks. Values are finite numbers (negatives allowed); NaN / +-Infinity / non-number fail closed. Every hot op allocates zero bytes after construction.

import { Fenwick } from '@zakkster/lite-logn';

const f = new Fenwick(1000);
f.update(10, 5);        // add 5 at index 10
f.update(20, 3);        // add 3 at index 20
f.prefix(15);           // -> 5   (sum of [0..15] inclusive)
f.prefix(-1);           // -> 0   (the empty-prefix base case)
f.rangeSum(10, 20);     // -> 8   (sum of [10..20] inclusive)
f.at(10);               // -> 5   (single element = prefix(10) - prefix(9))
f.set(10, 100);         // set index 10 to 100 (absolute)
f.prefix(20);           // -> 103

// O(n) LINEAR bulk build (not n incremental updates):
const g = Fenwick.build([1, 2, 3, 4, 5]);
g.rangeSum(1, 3);       // -> 9

| Member | Signature | Complexity | Notes | | --- | --- | --- | --- | | constructor | new Fenwick(length) | O(length) | length integer in [1, 2^31-1]. Allocates one Float64Array(length + 1), zero-initialized. | | update | update(i, delta) -> this | O(log n) | Add delta at 0-based index i (climb by i & -i). delta finite (typeof-guarded first); out-of-range i throws. | | prefix | prefix(i) -> number | O(log n) | Sum of [0, i] INCLUSIVE (descend by i & -i). prefix(-1) === 0; valid domain [-1, length). | | rangeSum | rangeSum(lo, hi) -> number | O(log n) | Sum of [lo, hi] INCLUSIVE both ends = prefix(hi) - prefix(lo-1). Throws on out-of-range or lo > hi. | | at | at(i) -> number | O(log n) | The single element = prefix(i) - prefix(i-1). Out-of-range i throws. | | set | set(i, value) -> this | O(log n) | Set element i to value (absolute), via update(i, value - at(i)). value finite; S1 magnitude budget (below). | | setFrom | setFrom(src, i) -> this | O(log n) | Element i := src[i] (src a Float64Array, read INSIDE -> 0 B/op, the zero-box sibling of set). Non-Float64Array src throws; same finite + S1 doors. | | search | search(target) -> index | O(log n) | The smallest i with prefix(i) >= target, an EXACT lower_bound over the library's own prefix() (the descent sums cells HIGH->LOW, bit-for-bit as prefix() does). Returns length iff target > total or target === +Infinity; target <= 0 -> 0. O(log n) ALWAYS -- a zero-run is spanned by O(log n) tree cells, never O(zero-run)/O(n). For exactly-representable sums (integers <= 2^53) it matches a BigInt oracle and never returns a zero-weight index for target > 0. For fractional weights the returned index's prefix is within one ULP of target (the sampling guarantee's float bound). Precondition (documented, NOT enforced): every element >= 0. NaN / non-number throws. Boxes its one target arg when the caller is not inlined -- use searchFrom for 0 B/op. | | searchFrom | searchFrom(src, i) -> index | O(log n) | target := src[i], read INSIDE -> 0 B/op (the slot sibling of search; lite-pick calls it per pick from a non-inlined site, where search's one arg box would be 16 B/pick). Identical semantics + doors, sharing the same body. Non-Float64Array src or out-of-range i throws; NaN src[i] throws; byte-identical state on a rejection. | | clear | clear() -> this | O(length) | Zeros every element in place, keeping capacity; resets the S1 magnitude bound. | | forEach | forEach(fn) -> void | O(n log n) | Visits (value, index, fenwick) in ascending index order (each element is an at walk). | | length | getter | O(1) | Element count this tree was sized for. | | Fenwick.build | build(values) -> Fenwick | O(n) | LINEAR bulk build (each cell adds itself to its parent in one forward pass); fails closed on a non-array-like, any non-finite value, or an over-budget sum |value| (S1). |

S1 overflow budget (Fenwick / Fenwick2D). A scalar upper bound on sum |element| is kept at the door: update adds |delta|, set / setFrom add |new - old|, build sets sum|v|, clear resets to 0; the budget is MAX_VALUE / 2 (1D) / MAX_VALUE / 4 (2D). The hot path pays one add and one compare. A write that would exceed the budget takes a COLD O(n) exact recompute that resets the drifted bound and either accepts the write or throws [lite-logn] with the state byte-identical -- so a finite input can no longer produce a sticky NaN. Near a true magnitude of ~1e308 the cold path can repeat under churn (disclosed).

SegmentTree

A segment tree: an associative range-query AND a point-update, BOTH O(log n), over a SINGLE flat Float64Array(2n) -- no nodes, no pointers, no recursion on the hot path. It is the complement to Fenwick: Fenwick's rangeSum works only because subtraction inverts addition, so it is a SUM machine; SegmentTree folds ANY associative + commutative operation over a range -- min / max / sum / gcd -- because it stores a fold of each subtree at its internal node rather than a prefix. The fold is chosen ONCE at construction and cached as a small-int combined by an INLINE switch on the hot path (no function ref, no closure, no megamorphic call site). Leaves live at _t[n + i]; internal node p holds the fold of its children _t[2p] / _t[2p+1], so _t[1] is the fold of the whole array and _t[0] is unused (null is not zero). update sets a leaf and climbs to the root recomputing each ancestor (one write per level); query walks the two boundaries up the tree, folding each node that lies fully inside [lo, hi] into one accumulator. Every hot op allocates zero bytes after construction.

The fold's identity fills query accumulators and cleared / fresh leaves -- sum -> 0, min -> +Infinity, max -> -Infinity, gcd -> 0 -- so a fresh or cleared tree queries to the identity. Identity is a legal RESULT but NEVER a legal INPUT: the value door rejects user NaN / +-Infinity (and, for the gcd kind, any negative or non-integer value), typeof-guarded before coercion.

import { SegmentTree } from '@zakkster/lite-logn';

const st = new SegmentTree(1000, 'min');   // 1000 slots, all +Infinity (min identity)
st.update(10, 5);        // set index 10 to 5 (absolute)
st.update(20, 3);        // set index 20 to 3
st.query(0, 999);        // -> 3   (min over [0..999] inclusive)
st.query(10, 10);        // -> 5   (a one-element range = the leaf)
st.at(20);               // -> 3   (the single leaf value, O(1))

// A different fold, chosen at construction:
const sum = SegmentTree.build([1, 2, 3, 4, 5], 'sum'); // O(n) bottom-up bulk build
sum.query(1, 3);         // -> 9   (2 + 3 + 4)
const g = SegmentTree.build([12, 18, 24], 'gcd');
g.query(0, 2);           // -> 6

The iterative 2n layout is order-agnostic -- query mixes left- and right-boundary contributions into one accumulator, so it is correct ONLY because min / max / sum / gcd are all COMMUTATIVE as well as associative. A future non-commutative fold (matrix product, string concat) would need a pow2 layout with separate ordered accumulators (see decisions/0005-segtree.md).

| Member | Signature | Complexity | Notes | | --- | --- | --- | --- | | constructor | new SegmentTree(length, kind) | O(length) | length integer in [1, 2^30-1] (HALF of Fenwick's ceiling: the 2n array must keep 2n a positive int32); kind is 'min' | 'max' | 'sum' | 'gcd'. Allocates one Float64Array(2 * length). | | query | query(lo, hi) -> number | O(log n) | The fold over [lo, hi] INCLUSIVE both ends. Throws on out-of-range or lo > hi. lo == hi returns that single leaf. | | update | update(i, value) -> this | O(log n) | Set leaf i to value (ABSOLUTE), then fix ancestors. value finite (nonnegative integer for the gcd kind); out-of-range i throws. The sum kind additionally bounds \|value\| <= MAX_VALUE / (2 * length) at the door (S1), so a full-range fold never overflows to Infinity / NaN. | | setFrom | setFrom(src, i) -> this | O(log n) | Leaf i := src[i] (src a Float64Array, read INSIDE -> 0 B/op, the zero-box sibling of update); same finite / gcd-domain / S1 doors. Non-Float64Array src throws. | | at | at(i) -> number | O(1) | The single leaf value. Out-of-range i throws. | | clear | clear() -> this | O(n) | Resets every element to the fold identity, keeping capacity. | | forEach | forEach(fn) -> void | O(n) | Visits (value, index, tree) in ascending leaf order. | | length / kind | getters | O(1) | Element count / the frozen fold 'min' | 'max' | 'sum' | 'gcd'. | | SegmentTree.build | build(values, kind) -> SegmentTree | O(n) | Bottom-up bulk build (seed leaves, then fold each internal node once deepest-first -- NOT n incremental updates); fails closed on a non-array-like, any non-finite value, or (gcd) any negative / non-integer. |

SkipList

A skip list: a pointer-free ordered map (key -> value) whose get / set / delete / successor / predecessor are expected O(log n) via a probabilistic tower of forward links -- the family's first randomized member and its first pointer-based one. Where the array-embedded members bury a fixed-shape tree in index arithmetic, a skip list's shape is random, so it needs real per-node links; the trick that keeps it zero-GC is storing those links as slot indices in flat Uint32Array columns over a private free-list (NodePool), never as heap objects. NIL = 0, slot 0 is the head sentinel, and level generation is one step of the repo's Numerical-Recipes LCG whose high bits draw a geometric height (1 + clz32(word)) -- deterministic from an instance-local seed, no Math.random. Keys are finite numbers (typeof-guarded before coercion; Symbol / BigInt / NaN / +-Infinity fail closed); values are finite numbers; set on an existing key updates the value in place (no new node). Every hot op allocates zero bytes after construction.

Honesty note: the hot ops are expected O(log n), not worst-case -- an unlucky seed can build a tall thin tower and spike a single op. The witness fits the clean average line and separately prints the MAX single insert over a realistic randomized build trace, so the expectation is never sold as a guarantee.

import { SkipList } from '@zakkster/lite-logn';

const sl = new SkipList(1000, 42);   // capacity 1000, seed 42 (deterministic)
sl.set(50, 500);                     // insert key 50 -> value 500
sl.set(20, 200);
sl.set(80, 800);
sl.get(20);            // -> 200
sl.set(20, 222);       // update value in