X-Fast Trie answers member/successor/predecessor
over a fixed universe in O(log log U) expected time, but costs O(n log U)
space — every one of the n stored values can plant a hash-table entry at every one of
w = log₂ U levels. A Y-fast trie keeps the exact same query time by
adding one layer of indirection: split the n values into small sorted buckets of
roughly w elements each, and build an X-fast trie over only the buckets'
representatives — each bucket's own maximum value — instead of over every value
directly. A query first finds the right bucket by asking the small representative trie a single
successor question, then finishes with a search inside that one bucket. Since there are only
O(n / w) representatives, the trie layer costs O(n), and the buckets
between them hold the other O(n) values directly — O(n) total, no
log U factor, for the identical query guarantee.
Same 16-value universe and the same preloaded set as the
X-Fast Trie and
Van Emde Boas Tree pages,
{2, 3, 5, 8, 14}, inserted in that order — this page keeps a bucket target size of
g = 3 (healthy range 2–6 elements; splits above 6, merges below 2), so all five start
out in a single bucket. Insert 6, then 7 to push it to 7 elements and watch it
split in two; then delete 7, 6, 5, and 3, in that order, to watch the shrinking
buckets merge back into one. The bottom grid is exactly X-Fast Trie's own 5-level
visualization, just fed representatives instead of raw values — insert, delete, or query a value
and step through to see the representative-trie lookup and the bucket search separately.
Only the representative gets a trie entry. A bucket's representative is defined
as its own current maximum — nothing more. Membership, successor, and predecessor for values that
aren't representatives are answered by first finding the right bucket, then searching
inside it; the representative trie never needs to know about any value that isn't currently a
bucket's max. On the preloaded set, buckets end up as [2, 3] (representative 3) and
[5, 8, 14] (representative 14) — only 3 and 14 ever touch
the trie below.
Finding the right bucket is one successor question. Because each bucket's
representative is its own maximum, and buckets are laid out in sorted, non-overlapping order, the
bucket that would contain a query value x is always the one whose representative is
the smallest representative that is still ≥ x — exactly what X-Fast Trie's
own predecessorSuccessor already computes as "successor," reused here without
modification, over the much smaller representative set. If x is itself a
representative, its own bucket is the answer directly; if x is larger than every
representative, no bucket can contain it.
The bucket search is small by construction. Every bucket is kept within a
target size band (this page uses 2–6 elements; a real implementation ties the band to
w = log₂ U, so roughly w/2 to 2w) — small enough that a
binary search inside it costs O(log w) = O(log log U), the same order as the
representative-trie lookup that found it. Two O(log log U) steps in sequence are still
O(log log U).
Splitting and merging keep the bucket count — and therefore the trie's own size — at
O(n / w), not just at construction time. An insert that pushes a bucket above
twice the target size splits it into two halves, each gets its own representative; a delete that
drops a bucket below half the target size merges it into a neighbor (splitting again immediately
if the merge overshoots). Skipping either rule doesn't break any single query — it just lets a
bucket grow or shrink without bound, and the whole point of the indirection quietly erodes. Built,
instrumented, and stress-tested at three universe sizes: with n = 2,000 values spread
over a 16-bit universe (U = 65,536, w = 16, g = 16), a plain
X-Fast Trie over all 2,000 values directly needs 13,472 hash-table node entries;
this page's Y-Fast Trie needs 1,014 node entries in its 89-representative trie
plus 2,000 bucket-array slots — 3,014 total, a measured
4.47× fewer node entries, with every bucket landing between 16 and 32 elements as
the split/merge band promises.
insert, member, predecessorSuccessor, and
longestMatch below are copied from X-Fast Trie's own reference
implementation without changes — see that page for how they work. delete is new:
that page never needed it (its own demo only ever grows), but a Y-fast trie's split/merge
maintenance has to remove a stale representative and install a new one, so this page had to build
and verify deletion for the first time.
class XFastTrie {
constructor(w) {
this.w = w;
this.U = 1 << w;
this.levels = []; // levels[j]: Map from j-bit prefix -> { missingSide, desc, count }
for (let j = 0; j <= w; j++) this.levels.push(new Map());
this.present = new Set();
this.prev = new Map(); // sorted doubly linked list over present values
this.next = new Map();
}
prefix(x, j) { return x >>> (this.w - j); }
bitAt(x, j) { return (x >>> (this.w - 1 - j)) & 1; }
longestMatch(x) {
let lo = 0, hi = this.w;
while (hi - lo > 1) {
const mid = (lo + hi) >> 1;
if (this.levels[mid].has(this.prefix(x, mid))) lo = mid; else hi = mid;
}
if (hi === this.w && this.levels[hi].has(this.prefix(x, hi))) lo = hi;
return lo;
}
member(x) {
if (this.levels[0].size === 0) return false;
return this.longestMatch(x) === this.w;
}
predecessorSuccessor(x) {
if (this.levels[0].size === 0) return { pred: null, succ: null };
const lo = this.longestMatch(x);
if (lo === this.w) {
const p = this.prev.get(x), s = this.next.get(x);
return { pred: p === -1 ? null : p, succ: s === this.U ? null : s };
}
const node = this.levels[lo].get(this.prefix(x, lo));
const bit = this.bitAt(x, lo);
if (bit === 0) {
const succ = node.desc;
const p = this.prev.get(succ);
return { pred: p === -1 ? null : p, succ };
} else {
const pred = node.desc;
const s = this.next.get(pred);
return { pred, succ: s === this.U ? null : s };
}
}
insert(x) {
if (this.present.has(x)) return;
if (this.levels[0].size === 0) {
this.levels[0].set(0, { missingSide: null, desc: null, count: 0 });
for (let j = 0; j < this.w; j++) {
const b = this.bitAt(x, j);
const node = this.levels[j].get(this.prefix(x, j));
node.missingSide = 1 - b; node.desc = x;
this.levels[j + 1].set(this.prefix(x, j + 1), { missingSide: null, desc: null, count: 0 });
}
for (let j = 0; j <= this.w; j++) this.levels[j].get(this.prefix(x, j)).count++;
this.present.add(x); this.prev.set(x, -1); this.next.set(x, this.U);
return;
}
const lo = this.longestMatch(x);
if (lo === this.w) return;
const node = this.levels[lo].get(this.prefix(x, lo));
const bit = this.bitAt(x, lo);
let pred, succ;
if (bit === 0) { succ = node.desc; const p = this.prev.get(succ); pred = p === -1 ? null : p; }
else { pred = node.desc; const s = this.next.get(pred); succ = s === this.U ? null : s; }
const predVal = pred === null ? -1 : pred, succVal = succ === null ? this.U : succ;
this.prev.set(x, predVal); this.next.set(x, succVal);
if (predVal !== -1) this.next.set(predVal, x);
if (succVal !== this.U) this.prev.set(succVal, x);
this.present.add(x);
for (let j = 0; j < lo; j++) {
const anc = this.levels[j].get(this.prefix(x, j));
anc.count++;
if (anc.missingSide === null) continue;
if (anc.missingSide === 0) { if (x < anc.desc) anc.desc = x; }
else { if (x > anc.desc) anc.desc = x; }
}
node.count++; node.missingSide = null; node.desc = null;
for (let j = lo + 1; j <= this.w; j++) {
const cur = { missingSide: null, desc: null, count: 1 };
if (j < this.w) { const b = this.bitAt(x, j); cur.missingSide = 1 - b; cur.desc = x; }
this.levels[j].set(this.prefix(x, j), cur);
}
}
// New for this page. Walk from the leaf up to the root, decrementing each ancestor's
// descendant count and dropping the node entirely once nothing real passes through it
// any more. A surviving ancestor whose OTHER side just emptied out becomes a new
// missingSide/desc pair; a surviving ancestor whose desc pointer WAS x (x was the extreme
// of the one subtree that's still non-empty) gets desc recomputed from x's own linked-list
// neighbor, which is guaranteed to still share this node's prefix.
delete(x) {
if (!this.present.has(x)) return;
const p = this.prev.get(x), s = this.next.get(x);
if (p !== -1) this.next.set(p, s);
if (s !== this.U) this.prev.set(s, p);
this.prev.delete(x); this.next.delete(x); this.present.delete(x);
for (let j = this.w; j >= 0; j--) {
const key = this.prefix(x, j);
const node = this.levels[j].get(key);
node.count--;
if (node.count === 0) { this.levels[j].delete(key); continue; }
if (j < this.w) {
const bit = this.bitAt(x, j);
const childExists = this.levels[j + 1].has(this.prefix(x, j + 1));
if (!childExists) {
node.missingSide = bit;
node.desc = (bit === 0) ? s : p;
} else if (node.missingSide !== null && node.missingSide !== bit && node.desc === x) {
node.desc = (bit === 0) ? p : s;
}
}
}
}
}
class YFastTrie {
constructor(w, g) {
this.w = w; this.U = 1 << w; this.g = g;
this.reps = new XFastTrie(w); // one representative per bucket
this.buckets = new Map(); // representative -> sorted array of real values
}
// The bucket that would hold x: itself, if x is a representative, else the smallest
// representative that's still >= x (X-Fast Trie's own "successor").
_bucketFor(x) {
if (this.reps.member(x)) return x;
return this.reps.predecessorSuccessor(x).succ;
}
member(x) {
if (this.reps.present.size === 0) return false;
const rep = this._bucketFor(x);
if (rep === null) return false;
const b = this.buckets.get(rep);
const i = lowerBound(b, x);
return i < b.length && b[i] === x;
}
predecessorSuccessor(x) {
if (this.reps.present.size === 0) return { pred: null, succ: null };
if (this.reps.member(x)) {
const b = this.buckets.get(x);
const pred = b.length > 1 ? b[b.length - 2] : this.reps.predecessorSuccessor(x).pred;
const nextRep = this.reps.predecessorSuccessor(x).succ;
const succ = nextRep === null ? null : this.buckets.get(nextRep)[0];
return { pred, succ };
}
const { pred: predRep, succ: succRep } = this.reps.predecessorSuccessor(x);
if (succRep === null) return { pred: predRep, succ: null };
const b = this.buckets.get(succRep);
const succVal = firstGreaterThan(b, x);
const predVal = lastLessThan(b, x);
return { pred: predVal === null ? predRep : predVal, succ: succVal };
}
_maybeSplit(rep) {
const b = this.buckets.get(rep);
if (b.length <= 2 * this.g) return;
const mid = b.length >> 1;
const left = b.slice(0, mid), right = b.slice(mid);
this.buckets.delete(rep); this.reps.delete(rep);
this.buckets.set(left[left.length - 1], left); this.reps.insert(left[left.length - 1]);
this.buckets.set(right[right.length - 1], right); this.reps.insert(right[right.length - 1]);
}
insert(x) {
if (this.member(x)) return;
if (this.reps.present.size === 0) { this.buckets.set(x, [x]); this.reps.insert(x); return; }
const rep = this._bucketFor(x);
if (rep === null) { // x beyond every representative
const oldRep = this.reps.predecessorSuccessor(x).pred;
const b = this.buckets.get(oldRep);
b.push(x);
this.buckets.delete(oldRep); this.reps.delete(oldRep);
this.buckets.set(x, b); this.reps.insert(x);
this._maybeSplit(x);
return;
}
const b = this.buckets.get(rep);
const pos = lowerBound(b, x);
b.splice(pos, 0, x);
if (pos === b.length - 1) { // x became this bucket's new max
this.buckets.delete(rep); this.reps.delete(rep);
this.buckets.set(x, b); this.reps.insert(x);
this._maybeSplit(x);
} else {
this._maybeSplit(rep);
}
}
_maybeMerge(rep) {
const b = this.buckets.get(rep);
if (b.length >= Math.ceil(this.g / 2) || this.buckets.size === 1) return;
const { pred: predRep, succ: succRep } = this.reps.predecessorSuccessor(rep);
const neighborRep = predRep !== null ? predRep : succRep;
const nb = this.buckets.get(neighborRep);
const merged = predRep !== null ? nb.concat(b) : b.concat(nb);
this.buckets.delete(rep); this.reps.delete(rep);
this.buckets.delete(neighborRep); this.reps.delete(neighborRep);
const newRep = merged[merged.length - 1];
this.buckets.set(newRep, merged); this.reps.insert(newRep);
this._maybeSplit(newRep);
}
delete(x) {
if (!this.member(x)) return;
let rep = this._bucketFor(x);
const b = this.buckets.get(rep);
b.splice(lowerBound(b, x), 1);
if (b.length === 0) { this.buckets.delete(rep); this.reps.delete(rep); return; }
if (rep === x) { // deleted value was this bucket's max
const newRep = b[b.length - 1];
this.buckets.delete(rep); this.reps.delete(rep);
this.buckets.set(newRep, b); this.reps.insert(newRep);
rep = newRep;
}
this._maybeMerge(rep);
}
}
function lowerBound(a, x) { let lo = 0, hi = a.length; while (lo < hi) { const m = (lo + hi) >> 1; if (a[m] < x) lo = m + 1; else hi = m; } return lo; }
function firstGreaterThan(a, x) { let lo = 0, hi = a.length; while (lo < hi) { const m = (lo + hi) >> 1; if (a[m] <= x) lo = m + 1; else hi = m; } return lo < a.length ? a[lo] : null; }
function lastLessThan(a, x) { let lo = 0, hi = a.length; while (lo < hi) { const m = (lo + hi) >> 1; if (a[m] < x) lo = m + 1; else hi = m; } return lo > 0 ? a[lo - 1] : null; }Verified against a plain sorted-array/Set reference across three universe sizes, checking
member and predecessorSuccessor for every possible value after
every single randomized insert or delete: 0 mismatches across 96,000
point-checks at w=4, 384,000 at w=6, and 1,152,000 at w=8
(300, 100, and 30 trials of 30/60/150 mixed insert-delete operations respectively). The extended
XFastTrie.delete itself was verified the same way, on its own, first — 96,000 +
256,000 + 614,400 point-checks across the same three sizes, 0 mismatches — before it was ever
wired into the Y-fast trie above, so a bug couldn't hide behind the bucket layer.
Letting a bucket's representative go stale the moment its maximum changes.
Inserting a new largest value into a bucket, or deleting the current largest value out of one,
changes what that bucket's maximum is — and the representative trie has to be told: delete
the old key, insert the new one. Skipping that update (just splicing the bucket's array and leaving
the representative trie's key exactly where it was) still finds a bucket for every query — it just
finds the wrong one as soon as a query value falls between the stale key and the real one.
Stress-tested by disabling only that update and running the same insert-only harness: 49.6%
of point-checks wrong at w=4, 49.1% at w=6 — roughly a coin
flip, since the bug only bites queries that land in the gap the stale key creates, and about half
of them do.
Routing a query to the representative at or below x instead of
at or above it. Since a bucket's representative is its maximum, the
bucket that could possibly contain x is the one whose representative is the smallest
one still ≥ x — reaching for X-Fast Trie's predecessor instead of its successor here
is an easy direction slip, and it still returns some bucket for almost every query, just
never the one that actually contains a value near x on the correct side. Stress-tested
the same way: 72.7% of point-checks wrong at w=4, 85.8% at
w=6 — worse at the larger size, since more buckets means more chances to land
in one that's simply the wrong neighbor.
Time: member, successor, and predecessor
are O(log log U) expected — an O(log log U) lookup in the representative
trie (identical to X-Fast Trie's own bound, just over O(n/w) keys instead of
n) to find the right bucket, plus an O(log(bucket size)) = O(log w) =
O(log log U) binary search inside it, since a real implementation keeps every bucket's size
within a constant factor of w. insert and delete are
O(log U) expected: whenever a bucket's maximum changes, or a split or merge fires, the
representative trie needs a full O(log U) insert or delete (see X-Fast Trie's own
Complexity section for why that operation can't be faster there), plus O(w) = O(log U)
to splice, split, or merge the bucket's own array.
Space: O(n) — the split/merge rule keeps every bucket's size within
a constant factor of w, which pins the number of buckets (and therefore
representatives) at O(n / w). X-Fast Trie's own space bound, O(k·(w+1))
for k stored keys, applied to k = O(n/w) representatives gives
O((n/w)·w) = O(n) for the trie layer; the buckets themselves hold the other
n values directly, one slot each. Total: O(n), no log U
factor anywhere — the entire reason this page exists on top of X-Fast Trie's O(n log
U), for the identical query guarantee.
This site's guide, Choosing a Range Query Structure, sets this entry aside the same way it already sets aside X-Fast Trie and Van Emde Boas Tree — a third mechanism for the identical membership/successor/predecessor-over-a-fixed-universe question, not a range query over a changing array.