Цифровой бор

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

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

Задача

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

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

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

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

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

---

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

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