XOR на отрезке

1. Идея

Нужно отвечать на много запросов вида: найти XOR всех элементов на отрезке [l, r].

Если для каждого запроса проходить по всему отрезку, то один запрос может работать за O(n), а все запросы — за O(nq). При n, q до 2 * 10^5 это слишком медленно.

Поэтому нужно заранее подготовить структуру, которая позволит быстро отвечать на запросы. Здесь отлично подходят префиксные XOR.

Определим массив pref, где:

• pref[0] = 0
• pref[i] = a_1 XOR a_2 XOR ... XOR a_i

Тогда XOR на отрезке [l, r] можно получить так:

pref[r] XOR pref[l - 1]

Это полностью аналогично префиксным суммам, только вместо сложения используется операция XOR.

2. Наблюдения

Наблюдение 1. Свойство XOR

Для любого числа x верно:

• x XOR x = 0
• x XOR 0 = x

Это ключевое свойство.

Наблюдение 2. Что хранит pref[r]

pref[r] — это XOR всех элементов от 1 до r:

a_1 XOR a_2 XOR ... XOR a_r

А pref[l - 1] — XOR всех элементов от 1 до l - 1:

a_1 XOR a_2 XOR ... XOR a_{l-1}

Если сделать XOR этих двух значений, то одинаковые элементы слева сократятся:

pref[r] XOR pref[l - 1]

(a_1 XOR ... XOR a_{l-1} XOR a_l XOR ... XOR a_r) XOR (a_1 XOR ... XOR a_{l-1})

Все элементы a_1 ... a_{l-1} встречаются дважды, значит уничтожаются, и остается только:

a_l XOR a_{l+1} XOR ... XOR a_r

То есть именно ответ на запрос.

Наблюдение 3. Все запросы можно обрабатывать за O(1)

Если массив pref уже построен, то для каждого запроса нужно только взять два числа и сделать один XOR.

3. Алгоритм

1. Считываем n и q.
2. Считываем массив a.
3. Строим массив префиксных XOR pref длины n + 1:
   • pref[0] = 0
   • для i от 1 до n:
     • pref[i] = pref[i - 1] XOR a[i - 1] в Python
     • или pref[i] = pref[i - 1] XOR x при чтении в C++
4. Для каждого запроса (l, r) выводим:
   • pref[r] XOR pref[l - 1]

4. Почему это работает

Докажем корректность.

Пусть:

• pref[r] = a_1 XOR a_2 XOR ... XOR a_r
• pref[l - 1] = a_1 XOR a_2 XOR ... XOR a_{l-1}

Тогда:

pref[r] XOR pref[l - 1]

равно

(a_1 XOR a_2 XOR ... XOR a_{l-1} XOR a_l XOR ... XOR a_r) XOR (a_1 XOR a_2 XOR ... XOR a_{l-1})

Так как XOR коммутативен и ассоциативен, можно перегруппировать одинаковые элементы. Для каждого a_i, где 1 <= i < l, получится:

a_i XOR a_i = 0

Все такие элементы сокращаются, и остается:

a_l XOR a_{l+1} XOR ... XOR a_r

Это и есть XOR на отрезке [l, r].

Значит, формула pref[r] XOR pref[l - 1] всегда дает правильный ответ.

5. Сложность

Построение

• Время: O(n)
• Память: O(n)

Ответы на запросы

• Каждый запрос: O(1)
• Все запросы: O(q)

Итог

• Общее время: O(n + q)
• Общая память: O(n)

Это укладывается в ограничения.

6. Код на C++17

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, q;
    cin >> n >> q;

    vector<long long> pref(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        long long x;
        cin >> x;
        pref[i] = pref[i - 1] ^ x;
    }

    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        cout << (pref[r] ^ pref[l - 1]) << '\n';
    }

    return 0;
}

7. Код на Python 3

n, q = map(int, input().split())
a = list(map(int, input().split()))

pref = [0] * (n + 1)
for i in range(1, n + 1):
    pref[i] = pref[i - 1] ^ a[i - 1]

for _ in range(q):
    l, r = map(int, input().split())
    print(pref[r] ^ pref[l - 1])