Бор с глобальными операциями

Глобальные операции над множеством чисел — «поксорить всё с $c$», «прибавить всем единицу» — по отдельности решаются ленивой величиной: обратимая операция переносится на вопрос, а не применяется к данным.

Вместе они так не складываются: $(x \oplus c) + v$ нельзя переписать как $(x + v')\oplus c'$. Сбрасывать накопленное в массив при каждой смене типа — это $O(n)$ на запрос. Здесь и нужен бор.

Устройство

Числа кладутся в двоичный бор, но биты записываются от младшего к старшему: на первом уровне — нулевой бит, на втором — первый, и так далее.

операция	что делать	стоимость
xor с $c$	запомнить маску, она меняет чтение битов	$O(1)$
прибавить единицу всем	обменять детей корня и уйти в перенос	$O(\log C)$
вычесть единицу у всех	то же, но спуск по заёму	$O(\log C)$
вставить и удалить число	обычный спуск по битам	$O(\log C)$

Почему прибавление единицы — это обмен

При $+1$ у всех чисел младший бит меняется на противоположный: это и есть обмен детей корня. У тех чисел, у которых он был единицей, случился перенос — и они все лежат в одном поддереве. Значит достаточно спуститься в него и повторить то же самое на следующем бите.

void increase(int node, int level) {
    if (!node || level == BITS) return;
    int ones = 1 ^ ((flip >> level) & 1);      // где сейчас лежат единицы
    std::swap(child[node][0], child[node][1]);
    increase(child[node][1 - ones], level + 1);
}

Спуск идёт ровно по одной ветке на уровень, поэтому вся операция — логарифм, а не размер множества.

Ленивый xor

Применить xor с $c$ значит обменять детей у всех вершин тех уровней, где у $c$ стоит единица. Делать это честно дорого, но и не нужно: держим маску flip и при любом спуске читаем бит как bit ^ ((flip >> level) & 1).

Маска участвует и в прибавлении: понять, в каком ребёнке лежат единицы, без неё нельзя.

Как достать значение элемента

Бор хранит значения, а спрашивают обычно про индекс. Держите для каждого индекса указатель на его лист и поднимайтесь к корню, собирая биты: на каждом шаге видно, каким ребёнком является вершина. Обмен детей эту сторону меняет — значит при обмене её надо править, это две записи.

Бор удобно завести полным: все $2^{B+1} - 1$ вершин созданы заранее, вставка ничего не создаёт, обмен — перестановка двух ссылок. При $B = 20$ это два миллиона вершин, зато ни мусора, ни аллокаций.

Где ещё пригодится

Тот же бор по битам решает «наибольший xor с данным числом» (спуск в противоположную ветку), «сколько пар с xor меньше $x$», «$k$-й по величине xor». Глобальные операции к ним добавляются бесплатно — маска и обмены работают независимо от того, что именно вы спрашиваете.

Смежное: исключающее ИЛИ, бор, битовые трюки.