Fusion Trees

Every computer-science student learns the same fact early: searching a sorted list of $n$ items takes $O(\log n)$ comparisons. That is not a gap in our cleverness — it is a proven lower bound. Any algorithm that can only ask "is $x < y$?" must make at least $\log_2 n$ such questions in the worst case.

But that lower bound has a fine print: it counts comparisons, not CPU operations. A real processor has something extra — it can manipulate whole words of $w$ bits in a single clock cycle. Can we exploit that?

In 1990 Michael Fredman and Dan Willard answered with a resounding yes. Their fusion tree stores $n$ integers in $O(n)$ space and answers predecessor queries in $O(\log_w n)$ time — a factor of $\log w$ faster than binary search, legally, because the proof never assumed word-level tricks were free. On a 64-bit machine that collapses 64 potential comparison levels into one. It was the first data structure to beat the comparison lower bound for integer searching.

The demo below builds a sorted set of integers stored in a fusion tree node. Each node holds up to $w^{1/5}$ keys (here $w = 32$, so up to 2 keys per node for clarity). Enter a query value and watch how the tree locates the predecessor — the largest stored key that is $\leq$ the query — in $O(\log_w n)$ steps rather than $O(\log n)$.

<p class="hint">{{hint}}</p>
<div class="controls">
  <label>{{label_keys}}
    <input id="keys-input" type="text" value="3, 10, 17, 28, 42, 55, 60, 77, 88, 99, 110, 120" />
  </label>
  <label>{{label_query}}
    <input id="query-input" type="number" min="0" max="127" value="62" />
  </label>
  <div class="btns">
    <button id="build-btn" type="button">{{btn_build}}</button>
    <button id="search-btn" type="button">{{btn_search}}</button>
    <button id="reset-btn" type="button" class="ghost">{{btn_reset}}</button>
  </div>
</div>
<div id="tree-vis"></div>
<div class="status" id="status">{{status_build_first}}</div>
<div class="log" id="log"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: flex; flex-direction: column; gap: .4rem; margin-bottom: .7rem; }
label { display: flex; flex-direction: column; gap: .2rem; font-size: .85rem; color: #555; }
input[type=text], input[type=number] {
  padding: .3rem .5rem; border: 1px solid #bbb; border-radius: 6px;
  font-size: .9rem; width: 100%; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
#tree-vis { overflow-x: auto; min-height: 60px; margin: .5rem 0; }
svg.tree { display: block; }
.status { font-size: .95rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.log { font: .78rem ui-monospace, monospace; color: #555; line-height: 1.5;
       max-height: 90px; overflow-y: auto; border-top: 1px solid #e0e4e8;
       padding-top: .3rem; white-space: pre-wrap; }

// Code not found

Notice: the classic binary search makes one comparison per level, visiting $\log_2 n$ nodes. The fusion tree sketches all branch-keys in a node into a single integer and finds the right child with bitwise arithmetic — one CPU instruction covers what binary search does in $\log w$ comparisons. That is the comparison-bound loophole Fredman and Willard exploited.

How does a fusion tree actually beat the comparison bound?

• The comparison lower bound says any decision tree that only branches on $x < y$ needs $\Omega(\log n)$ leaves to distinguish $n$ keys. This is a genuine theorem — you cannot escape it inside the comparison model.
• The word-RAM model adds one extra assumption: the computer can manipulate $w$-bit integers in $O(1)$ time. This is what every real CPU does, and it breaks the proof.
• Sketching. A fusion tree node holds $B = w^{1/5}$ keys. The crucial trick is to sketch all $B$ branch-keys into a single $w$-bit integer by extracting only the $B^4$ bits that distinguish them. The sketch of a query can then be compared to all $B$ sketches simultaneously using one multiply-and-mask sequence — $O(1)$ word operations.
• Finding the right child. After the parallel comparison, a single rank operation (also $O(1)$ words) tells you which child to descend into. Each node reduces the problem by a factor of $B = w^{1/5}$, so the tree has depth $\log_B n = \log n / \log w = \log_w n$.
• Result (proven, 1990). Fredman and Willard showed that $n$ integers in the word-RAM model support predecessor queries in $\Theta(\log_w n)$ time and $O(n)$ space. This is optimal for the word-RAM model; later work (Beame & Fich, 2002) proved no polynomial-space structure can do better for predecessor search.

The status: proven — Fredman & Willard (1990). Not an open problem, not a conjecture. A clean separation between two computational models with a matching lower bound from Beame & Fich.

Compare this to the sorting lower bound: sorting by comparisons also hits $\Omega(n \log n)$, but integer sorting can exploit word tricks too — radix sort runs in $O(n \log_w n)$, the same gain fusion trees give for search.

Word-level parallelism is not just an academic curiosity — it powers real systems:

• Integer sorting: packing the fusion-tree idea into sorting gives $O(n \log_w n)$ integer sort — faster than comparison-based $O(n \log n)$ sorts on large integers.
• IP routing tables: routers must find the longest-prefix match for a 32- or 128-bit address among millions of rules. Predecessor structures on tries exploit exactly the same word tricks to keep lookups fast.
• Compressed indexes: suffix arrays and BWT-based full-text indexes use predecessor search internally; word-parallel variants speed up genomic search engines.
• Competitive programming: when the key universe is bounded integers and $n$ is large, replacing a std::set (binary search tree, $O(\log n)$) with a van Emde Boas tree or a fusion-tree-inspired structure can make the difference between TLE and AC.
• Theory of lower bounds: fusion trees are the canonical example showing that the comparison model and the word-RAM model are genuinely different — a lesson that echoes through the study of P vs NP and the search for lower bounds everywhere in complexity theory.

Once you understand fusion trees, you understand why the comparison lower bound is a theorem about one model, not about all computers.

Fusion trees deliver a humbling reminder: the theorems we trust are theorems about a model, and reality sometimes offers a richer model than the one we assumed.

The $O(\log n)$ comparison bound is true and important. But the moment you let a CPU do what CPUs actually do — crunch 64 bits in one clock — the bound dissolves. Fredman and Willard turned that loophole into a provably optimal data structure, and Beame & Fich later confirmed that $\Theta(\log_w n)$ is the best any polynomial-space structure can do in the word-RAM model.

So the next time a textbook tells you "search is $O(\log n)$", ask: $\log n$ what? Comparisons? Yes. Word operations? Not necessarily. The distinction between models is where the most interesting separations in all of P vs NP research live, and fusion trees are one of the clearest places to see it.