Цифровой бор

Материал из Algocode wiki
Перейти к: навигация, поиск

Мы уже познакомились с бором, в некоторых задачах появляется идея хранить числа в боре, как строке, такая структура называется цифровой бор. Чаще всего числа надо записывать в двоичной системе счисления и тогда все очень просто, но в некоторых задачах требуется какая-то другая Система счисления, так как сравнивать числа в лексикографическом порядке в 10 системе счисления нельзя(2 > 11), то давайте заранее считать, что все числа $ < 10^x$ и тогда будем просто добивать число ведущими нулями. Теперь 02 < 11.

Какие же задачи можно решать такой структурой :

Задача

Дан массив чисел, подаются три вида запросов :

1) Добавить число $x$ 2) Удалить число $x$ 3) Найти число в массиве, у которого $\bigoplus$ c $x$ максимален

Первые 2 вида запросов мы умеем легко делать в цифровом боре.

Запрос третьего типа уже сложнее.

Заметим, что если мы можем взять $a$ из массива чисел, такой что $(a_{i}) != (x_{i})$(то есть они не равны в $i$-ом бите), то это выгоднее, чем взять любое число $b$, такое что $(b_{i}) = (x_{i}$ и при этом префикс $b$ до $i$ бита равен префиксу $a$ до $i$ бита, тогда давайте жадно спускаться по бору, каждый раз пытаясь пойти в ветку у которой $i$ бит не равен $i$-му биту $x$.



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin