Рассмотрим <tex>y</tex>. У него есть существенные биты и некоторый элемент <tex>x</tex>, с которым у <tex>y</tex> наибольший общий префикс (настоящий, а не по <tex>sketch</tex>). Биты из <tex>sketch</tex>, находящиеся в префиксе совпадают, значит <tex>succ</tex> и <tex>pred</tex> <tex>y</tex> среди <tex>sketch</tex> должны быть такими же среди <tex>x</tex>, и один из них имеет дальше бит <tex>0</tex> (а другой <tex>1</tex>) и с ним может быть больше других общих бит в <tex>sketch</tex>. То есть либо <tex>succ</tex>, либо <tex>pred</tex> имеют следующий существенный бит такой же, как и у <tex>y</tex>. Поэтому если значение равно <tex>0</tex>, то <tex>x</tex> наибольший среди значений с меньшим <tex>sketch</tex>, и, аналогично для <tex>1</tex>, наименьший среди больших.
}}
[[Файл:Fusion01.png|350x230px|thumb|right|Пример случая, когда <tex>succ(y)</tex> и <tex>pred(y)</tex> по <tex>sketch(y)</tex> не являются <tex>succ</tex> или <tex>pred</tex> по <tex>y</tex>]]
[[Файл:FusionTree.png|400x400px|thumb|right|Пример случая, когда <tex>sketch(a_i) \leqslant sketch(q) \leqslant sketch(a_{i+1})</tex>, но <tex>a_{i+1}\leqslant q</tex> <tex>sketch(a_i) = 00, sketch(q) = 00, sketch(a_{i+1}) = 01, \\ a_i = 0000, a_{i+1} = 0010, q = 0101</tex> ]]
}}
Первые два условия необходимы для того, чтобы сохранить все существенные биты в нужном порядке. Третье условие позволит поместить <tex>sketch</tex> узла в <tex>w</tex>-битный тип. Так как <tex>r \leqslant B-1</tex>, то <tex>sketch(node)</tex> будет занимать <tex>B(r^4 + 1) \leqslant B((B-1)^4 + 1) = B((B^2 - 2B + 1)^2 + 1)=</tex><tex>B(B^4 + 4B^2 + 1 - 4B^3 + 2B^2 -4B + 1) = B^5 - 4B^3 + 6B^2 - 4B + 2 \leqslant B^5 </tex><tex> = (w^{1/5})^5 = w </tex> бит, при всех <tex>B \geqslant 1</tex>
==Индекс наиболее значащего бита==
Чтобы найти в <tex>w</tex>-битном числе <tex>x</tex> индекс самого старшего бита, содержащего единицу (это понадобится в дальнейшем, для нахождения <tex>sketch(y)</tex> ), разделим <tex>x</tex> на <tex>\sqrt{w}</tex> блоков по <tex>\sqrt{w}</tex> бит. <tex>x = \underbrace{0101}_{\sqrt{w}}\; \underbrace{0000}_{\sqrt{w}}\; \underbrace{1000}_{\sqrt{w}}\; \underbrace{1101}_{\sqrt{w}}</tex>. Далее найдем первый непустой блок и индекс первого единичного бита в нем.
# Поиск непустых блоков.
##Определим, какие блоки имеют единицу в первом бите. Применим побитовое <tex>\&</tex> к <tex>x</tex> и константе <tex> F </tex>: <tex>
$$
\begin{array}{r}
\&
\begin{array}{r}
x = 0101\; 0000\; 1000\; 1101\\
F = 1000\; 1000\; 1000\; 1000\\
\end{array}\\
\hline
\begin{array}{r}
t_1 = \underline{0}000\; \underline{0}000\; \underline{1}000\; \underline{1}000 \end{array}\end{array}
$$</tex>
##Определим, содержат ли остальные биты единицы.
###Вычислим <tex>x \oplus t_1</tex>: <tex>
$$
\begin{array}{r}
\oplus
\begin{array}{r}
t_1 = 0000\; 0000\; 1000\; 1000\\
x = 0101\; 0000\; 1000\; 1101\\
\end{array} \\
\hline
\begin{array}{r}
t_2 = 0\underline{101}\; 0\underline{000}\; 0\underline{000}\; 0\underline{101}
\end{array}
\end{array}
$$</tex>
### Вычтем из <tex>F\; t_2</tex>. Если какой-нибудь бит <tex>F</tex> обнулится, значит, соответствующий блок содержит единицы: <tex>
$$
\begin{array}{r}
-
\begin{array}{r}
F = 1000\; 1000\; 1000\; 1000\\
t_2 = 0\underline{101}\; 0\underline{000}\; 0\underline{000}\; 0\underline{101}\\
\end{array} \\
\hline
\begin{array}{r}
t_3 = \underline{0}xxx\; \underline{1}000\; \underline{1}000\; \underline{0}xxx
\end{array}
\end{array}
$$</tex>
###Чтобы найти блоки, содержащие единицы, вычислим <tex>t_3 \oplus F</tex>: <tex>
$$
\begin{array}{r}
\oplus
\begin{array}{r}
F = 1000\; 1000\; 1000\; 1000\\
t_3 = \underline{0}xxx\; \underline{1}000\; \underline{1}000\; \underline{0}xxx\\
\end{array} \\
\hline
\begin{array}{r}
t_4 = \underline{1}000\; \underline{0}000\; \underline{0}000\; \underline{1}000
\end{array}
\end{array}
$$</tex>
##Первый бит в каждом блоке <tex>y = t_1 \lor t_4</tex> содержит единицу, если соответствующий блок <tex>x</tex> ненулевой: <tex>$$
\begin{array}{r}
\lor
\begin{array}{r}
t_1 = \underline{0}000\; \underline{0}000\; \underline{1}000\; \underline{1}000\\
t_4 = \underline{1}000\; \underline{0}000\; \underline{0}000\; \underline{1}000\\
\end{array} \\
\hline
\begin{array}{r}
y = \underline{1}000\; \underline{0}000\; \underline{1}000\; \underline{1}000
\end{array}
\end{array}
$$</tex>
# Найдем <tex>sketch(y)</tex>, чтобы сместить все нужные биты в один блок. Существенными битами в данном случае будут первые биты каждого блока, поэтому <tex>b_i = \sqrt{w} - 1 + i\sqrt{w}</tex>. Будем использовать <tex>m_j = w - (\sqrt{w}-1) - j\sqrt{w} +j</tex>. Тогда <tex>b_i + m_j = w + (i - j)\sqrt{w} + j</tex>. Все суммы различны при <tex>0\leqslant i, j < \sqrt{w} </tex>. Все <tex>b_i + m_i = w + i</tex> возрастают, и <tex>(b_{\sqrt{w} - 1} + m_{\sqrt{w} - 1}) - (b_0 + m_0) = \sqrt{w} - 1</tex>. Чтобы найти <tex>sketch(y)</tex>, умножим <tex>y</tex> на <tex>m</tex> и сдвинем вправо на <tex>w</tex> бит.
# Найдем первый ненулевой блок. Для этого надо найти первую единицу в <tex>sketch(y)</tex>. Как и при поиске <tex>succ(sketch(q))</tex> и <tex>pred(sketch(q))</tex> используем параллельное сравнение <tex>sketch(y)</tex> с <tex>2^0, 2^1 \ldots 2^{\sqrt{w} - 1}</tex>. В результате сравнения получим номер первого ненулевого блока <tex>c</tex>.
#Найдем номер <tex>d</tex> первого единичного бита в найденном блоке так же как и в предыдущем пункте.
#Индекс наиболее значащего бита будет равен <tex>c\sqrt{w}+d</tex>.
Каждый шаг выполняется за <tex>O(1)</tex>, поэтому всего потребуется <tex>O(1)</tex> времени, чтобы найти индекс.
== Индекс наиболее старшего бита с помощью цикла де Брёйна ==
