Бор

К разделу

Нужна структура для множества (или словаря) строк, где помимо ответа на вопрос «есть ли строка S?» можно также ответить на вопросы про префиксы: сколько слов начинается с какого-то префикса, перечислить их, дополнить структуру новым словом.

Примем следующие обозначения:

$Σ$ — алфавит, $| Σ |$ — его размер
$k$ — число строк в наборе;
$n$ — суммарная длина всех строк;
$| S |$ — длина запроса.

1. Определение и структура

Бор (префиксное дерево, нагруженное дерево, trie) — подвешенное дерево, у которого:

на каждом ребре записан символ алфавита;
у одной вершины нет двух исходящих ребер с одинаковым символом;
часть вершин помечены терминальными - это вершины, в которых заканчиваются какие-то слова из набора строк

Бор хранит ровно те строки, которые получаются, если выписать подряд символы на пути от корня до терминальной вершины.

(В некоторых источниках символ хранят не на ребре, а в вершине-ребенке. Это эквивалентно: символ ребра «корень → v» — это символ вершины v. Мы пишем символы на ребрах.)

Пример. Набор ${h e, s h e, h i s, h e r s}$ :

бор

Из определения строения бора следует:

Общие префиксы хранятся один раз — отсюда экономия по сравнению со списком строк.
Терминальность нужна отдельно: в примере he — префикс hers, но и сам элемент набора; вершина he не лист, но терминальна. Листья всегда терминальны.
Вершин не больше n + 1, глубина равна длине самой длинной строки.
Строку однозначно определяет путь, поэтому ее не нужно хранить в вершине.

В каждой вершине будут хранится ссылки на детей (переходы по какому-то символу), bool терминальности + еще какие-то переменные в зависимости от задачи

2. Операции

2.1 Вставка

Идем от корня по символам строки. Если перехода нет — создаем вершину. В конце отмечаем последнюю вершину терминальной.

Допустим есть два слова: gene и genetic. В зависимости от того в каком порядке вставляем слова получится два случая:

вставляем genetic, когда есть gene: идем по gene, создаем вершины $t$ , $i$ , $c$ , отмечаем $c$ ;
вставляем gene, когда есть genetic: новых вершин нет, только отметка терминальности.

Время: $O (| S |)$ — ровно $| S |$ шагов, на каждом $O (1)$ при хранении переходов массивом.

2.2 Поиск

Идем по символам. Возможны три исхода:

Не нашли переход — строки в боре нет.
Дошли до конца строки, но вершина не терминальна — строки нет (это лишь префикс другой строки).
Дошли до конца строки в терминальной вершине — строка есть.

Время: $O (| S |)$ , и не зависит ни от $k$ , ни от $n$ . Обход в глубину или ширину для поиска не нужен: путь целиком определен входной строкой.

3. Бинарный бор и задачи на XOR

3.1 Идея

Алфавит состоит из двух символов — {0, 1}. Целое неотрицательное число $x < 2^{B}$ рассматриваем как строку из ровно $B$ бит, от старшего к младшему. Все строки одной длины, поэтому ни одна не является префиксом другой: терминальны только листья на глубине $B$ , отдельный признак терминальности не нужен.

В вершине храним двух детей и счетчик cnt — сколько чисел проходит через вершину.

Вставка, поиск и удаление: $O (B)$ , не зависят от числа элементов.

Полезные свойства:

DFS с порядком «сначала 0, потом 1» выдает числа*по возрастанию
минимум — идти всегда в 0 (если можно), максимум — в 1;
k-й по величине элемент и «сколько элементов меньше x» — спуск по cnt, как в дереве порядковых статистик.

3.2 Задача 1. Максимальный XOR числа x с элементом множества

Дано: непустое множество чисел и число x. Найти: max по y из множества значение $x \oplus y$ .

Идем от старшего бита к младшему. На каждом шаге хотим, чтобы бит результата был 1, то есть выбрать ребенка с битом, противоположным биту $x$ . Если такой ребенок есть (и в его поддереве есть элементы) — идем в него; иначе — в единственный оставшийся.

Единица в бите $b$ дает вклад $2^{b}$ , а все младшие биты вместе дают не более $2^{b} - 1 < 2^{b}$ . Значит, любой вариант со старшей единицей лучше любого варианта без нее, и решение можно принимать бит за битом, не заглядывая вперед.

3.3 Задача 2. Максимальный XOR пары в массиве

Кладем в бор все числа массива и для каждого делаем max_xor из прошлой задачи, либо идем слева направо и запрашиваем max_xor до вставки очередного числа.

Сложность будет $O (n \cdot B)$ , тогда как перебор пар — $O (n^{2})$ .

3.4 Задача 3. Максимальный XOR подотрезка

XOR отрезка a[l..r] равен p[r] ⊕ p[l−1], где p[i] — XOR префикса длины i (p[0] = 0). Значит, задача сводится к предыдущей на массиве префиксных XOR.

Время и память $O (n \cdot B)$ .

Бор ​

1. Определение и структура ​

2. Операции ​

2.1 Вставка ​

2.2 Поиск ​

3. Бинарный бор и задачи на XOR ​

3.1 Идея ​

3.2 Задача 1. Максимальный XOR числа x с элементом множества ​

3.3 Задача 2. Максимальный XOR пары в массиве ​

3.4 Задача 3. Максимальный XOR подотрезка ​

Бор