317
правок
Изменения
Нет описания правки
* у всех вершин, кроме листьев, <tex>B = w^{1/5}</tex> детей,
* время, за которое определяется, в каком поддереве находится вершина, равно <tex>O(1)</tex>.
Такое время работы достигается за счет хранения дополнительной информации в вершинах. Построим [[:Сверхбыстрый_цифровой_бор|цифровой бор]] из ключей узла дерева. Всего <tex>B - 1</tex> ветвящихся вершин. Биты, соответствующие уровням дерева, в которых происходит ветвление, назовем существенными и обозначим их номера <tex>b_0, b_1\ldots b_{r-1}</tex> (индексация идет от листьев, которые соответствуют началу концу числа, т.е. старшему младшему разряду). Количество существенных битов <tex>r</tex> не больше <tex>B - 1</tex> (все ребра на уровне детей ветвящейся вершины ({{---}} обведены на рисунке) {{---}} являются существенными битами, и так как ветвящихся вершин <tex>B - 1</tex>, значит, и количество уровней с детьми не больше <tex>B - 1</tex>, поскольку на одном уровне могут быть несколько ветвящихся вершин).
[[Файл:Fusion.png||500x400px|center|визуализация функции sketch]]
Пусть <tex>\left \{ a_1,a_2\ldots a_k\right \}</tex> {{---}} множество ключей узла, отсортированных по возрастанию, <tex>q</tex> {{---}} ключ искомой вершины, <tex>l</tex> {{---}} количество бит в <tex>sketch(q)</tex>. Сначала найдем такой ключ <tex>a_i</tex>, что <tex>sketch(a_i) \leqslant sketch(q) \leqslant sketch(a_{i+1})</tex>. Хотя положение <tex>sketch(q)</tex> среди <tex>sketch(a_j)</tex> не всегда эквивалентно положению <tex>q</tex> среди <tex>a_j</tex>, зная соседние элементы <tex>sketch(q)</tex>, мы можем найти <tex>succ(q)</tex> и <tex>pred(q)</tex>.
===Понятия succ(q) Поиск следующего и pred(q)предыдущего===Пусть <tex>sketch(a_i) \leqslant sketch(q) \leqslant sketch(a_{i+1})</tex>.
{{Утверждение
|id=prefix.
|author=
|about=
|statement=Среди Пусть <tex>sketch(a_i) \leqslant sketch(q) \leqslant sketch(a_{i+1})</tex>. Тогда среди всех ключей наибольший общий префикс с <tex>q</tex> будет иметь или <tex>a_i</tex> или <tex>a_{i+1}</tex>.
|proof=
Предположим, что <tex>y</tex> имеет наибольший общий префикс с <tex>q</tex>. Тогда <tex>sketch(q)</tex> будет иметь больше общих битов со <tex>sketch(y)</tex>. Значит, <tex>sketch(y)</tex> ближе по значению к <tex>sketch(q)</tex>, чем <tex>sketch(a_i)</tex> или <tex>sketch(a_{i+1})</tex>, что приводит к противоречию.
Если <tex>sketch(a_i)< sketch(q)</tex>, то <tex>c_i = 0</tex>, в противном случае <tex>c_i = 1</tex>.
Теперь надо найти количество единиц в <tex>L</tex>. Умножим <tex>L</tex> на <tex>\underbrace{0\ldots 01}_{l + 1 bits}\ldots \underbrace{0\ldots 01}_{l+1 bits}</tex>, тогда все единицы сложатся в первом блоке результата, и, чтобы получить количество единиц, сдвинем его вправо на <tex>(k-1)*\cdot(l + 1)</tex> бит.
==Вычисление sketch(x)==
Чтобы получить <tex>m_i</tex>, выбираем каждый раз наименьшее <tex>m_i'</tex> и прибавляем подходящее число кратное <tex>r^3</tex>, такое что <tex>m_i+c_i < m_{i+1}+c_{i+1} \leqslant m_i+c_i+r^3</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) \leqslant B^5 = (w^{1/5})^5 = w </tex> бит.
==Индекс наиболее значащего бита==
