Разложение по битам

XOR на отрезке и сумма: когда пометки не существует, задача распадается на двадцать независимых деревьев.

2 мин

Операция XOR с числом $x$ на отрезке, запрос — сумма на отрезке. Пометки для этого не существует.

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

Каждый бит отдельно

У XOR есть свойство, которого нет у сложения: он действует на каждый бит независимо. А сумма по битам раскладывается:

\sum_{i=l}^{r} a_i = \sum_{b} 2^b \cdot c_b, \qquad c_b = |\{ i \in [l, r] : \text{бит } b \text{ у } a_i \text{ равен единице} \}|.

Для каждого бита заведём дерево, хранящее количество единиц. XOR с $x$ — это переворот тех битов, где у $x$ единица.

void applyFlip(int v, int tl, int tr) {
    ones[v] = (tr - tl + 1) - ones[v];
    flip[v] ^= 1;
}

Пометка булева, композиция — исключающее ИЛИ: два переворота отменяют друг друга. Это самая простая алгебра пометок, какая бывает.

Одно дерево вместо двадцати

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

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

void apply(int v, int len, int mask) {
    for (int b = 0; b < BITS; b++)
        if (mask >> b & 1) count[v][b] = len - count[v][b];
    lazy[v] ^= mask;
}

Спусков по дереву столько же, сколько в обычной задаче, а вся работа с битами происходит внутри узла, где данные лежат рядом. Счётчики удобно держать плоским массивом count[v * BITS + b].

Когда раскладывать по битам

Признак — побитовая операция в изменении и арифметическая в запросе: XOR и сумма, XOR и количество единичных битов.

Если обе операции побитовые, разложение обычно не нужно — операция и так поэлементна. Если обе арифметические, оно не поможет: сложение перемешивает биты переносами.

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