Дерево отрезков на xor с точечным обновлением — есть ли подвох по сравнению с суммой?
Хочу дерево отрезков на побитовый xor отрезка с точечными обновлениями (присвоить новое значение элементу, спрашивать xor на [l, r]). Это же ровно как сумма, только операция ^? Или есть подводные камни с нейтралью и переполнением?
2 ответа
Да, по структуре это в точности дерево на сумму, где + заменён на ^. Xor ассоциативен и коммутативен, нейтральный элемент — 0 (x ^ 0 = x). Переполнения нет: xor не увеличивает разрядность, результат влезает в тот же тип, что и операнды.
int t[4*N], a[N];
void build(int v, int tl, int tr) {
if (tl == tr) { t[v] = a[tl]; return; }
int tm = (tl + tr) / 2;
build(2*v, tl, tm); build(2*v+1, tm+1, tr);
t[v] = t[2*v] ^ t[2*v+1];
}
void update(int v, int tl, int tr, int pos, int val) {
if (tl == tr) { t[v] = val; return; }
int tm = (tl + tr) / 2;
if (pos <= tm) update(2*v, tl, tm, pos, val);
else update(2*v+1, tm+1, tr, pos, val);
t[v] = t[2*v] ^ t[2*v+1];
}
int query(int v, int tl, int tr, int l, int r) {
if (l > r) return 0; // нейтраль xor
if (l == tl && r == tr) return t[v];
int tm = (tl + tr) / 2;
return query(2*v, tl, tm, l, min(r,tm))
^ query(2*v+1, tm+1, tr, max(l,tm+1), r);
}
build O(n), update/query O(log n), память O(n). Поскольку xor обратим (a ^ a = 0), для точечных обновлений тут даже проще обойтись деревом Фенвика — оно короче и быстрее по константе.
Подвох появляется не с самим xor, а если в задаче нужен xor на отрезке с обновлением на отрезке (применить xor значения ко всем a[l..r]). Тут lazy-пометка «xor d на весь узел» ведёт себя нетривиально: xor значения d ко всем элементам узла меняет результат xor узла в зависимости от чётности длины узла. Если длина чётная, d ^ d ^ ... ^ d (чётное число раз) = 0, и xor узла не меняется; если нечётная — меняется на d.
void apply(int v, int tl, int tr, int d) {
if ((tr - tl + 1) & 1) t[v] ^= d; // меняется только при нечётной длине
lazy[v] ^= d; // пометки xor складываются по xor
}
Пометки xor накапливаются операцией xor (нейтраль 0), проталкивание стандартное. Вот это — реальная тонкость, на которой легко получить WA, в отличие от тривиального точечного случая. Про идемпотентность: xor не идемпотентен (x ^ x = 0 ≠ x), поэтому sparse table для xor с перекрытием некорректна — нужен либо Фенвик/дерево отрезков, либо disjoint sparse table.