XOR базис з видаленнями

Передмова

Ця стаття використовує терміни лінійної алгебри. Якщо ви їх розумієте, можете пропустити цей розділ.

Вступ

Згадаємо таку відому задачу:

Детальніше про те як розв'язувати цю задачу можна дізнатися за посиланням.

В цій статті будемо розглядати більш складну задачу, де ще є запити видалення числа з множини $S$. Крім того, ми отримуємо наступний запит, тільки після того, як відповіли на попередній (тобто задачу треба розв'язувати "в онлайні").

Початкову задачу можна розв'язувати за $O(m)$ на запит, а от задачу з видаленнями будемо навчатися розв'язувати за $O(m^2)$.

Структура

У задачі з видаленнями в нас починаються невизначеності на моменті, коли число, що ми додаємо до XOR базису представляється $\mathrm{xor}$-ами наявних чисел.

Ми хочемо ефективно зберегти кожне число, що додається до $S$, тому будемо підтримувати послідовність $X_n(n\ge 1)$ XOR базисів (кожен з яких є початково порожнім), замість одного базису.

Додавання числа $v$ до $S$

Розглянемо як саме будемо додавати нове число $v\ne 0$ до множини $S$:

1. Будемо поступово обходити по нашим базисами починаючи з першого. Нехай $i$ — номер поточного базису, який розглядаємо;

2. Якщо $v\notin \mathrm{span}(X_i)$, то просто додамо $v$ до $X_i$ і закінчимо процедуру;

3. Інакше, $v\in \mathrm{span}(X_i)$, то так додати не виходить, але ми прагнемо обов'язково десь зберегти це число. Тому збільшуємо $i$ на $1$ та повертаємося до кроку $2$.

Іншими словами, ми знаходимо таке мінімальне $i$, що $v\notin \mathrm{span}(X_i)$ та додаємо $v$ до $X_i$. Якщо в лоб реалізувати цей алгоритм, то в гіршому випадку він буде працювати за $O(|S|)$, що досить неефективно.

Будемо покращувати цей алгоритм. Спершу розглянемо деякі властивості даної послідовності базисів $X_n$:

Використовуючи ці дві властивості можна покращити алгоритм, щоб додавання працювало за $O(m^2)$ або навіть $O(m\log m)$.

Нагадаємо, що ми знаходимо таке мінімальне $i$, що $v\notin \mathrm{span}(X_i)$ та додаємо $v$ до $X_i$. Оскільки унікальних $\mathrm{span}(X_i)$ не більше $m+1$, то треба лише перебирати ті $i$, для яких $i=1$ або $\mathrm{span}(X_i)\ne \mathrm{span}(X_{i-1})$. Тоді досягнемо складності $O(m^2)$. Якщо використати бінарний пошук по цим індексам $i$, то досягнемо складності $O(m\log m)$.

Отже, ми навчилися додавати число $v\ne 0$ до множини $S$.

Видалення числа $v\in S$

Оберемо $j$, так що $v\in X_j$. Якщо просто видалити $v$ з $X_j$, то порушаться властивості, що зазначили попередньо. Ми будемо прагнути, щоб ці властивості виконувались після видалення.

Будемо видаляти таким чином:

1. Поки $\mathrm{span}(X_j)=\mathrm{span}(X_{j+1})$, то міняємо місцями базиси $X_j$ та $X_{j+1}$ ($\mathrm{swap}(X_j,X_{j+1})$) та збільшуємо $j$ на $1$. Оскільки $\mathrm{span}(X_j)=\mathrm{span}(X_{j+1})$, то неважливо в якому порядку розташовані ці базиси у послідовності, тому можна довільно їх перемішувати;

2. Тепер $\mathrm{span}(X_j)\ne \mathrm{span}(X_{j+1})$. Маємо два випадки:

   1. $\mathrm{span}(X_j\setminus \{v\})\supseteq \mathrm{span}(X_{j+1})$. В цьому випадку можемо просто видалити число $v$ з $X_j$ та закінчити процедуру;

   2. $\mathrm{span}(X_j\setminus \{v\})⊉\mathrm{span}(X_{j+1})$. Розглянемо одне твердження:

      Знайдемо цей $y\in X_{j+1}$ з твердження. Тоді можемо замінити $v$ у $X_j$ на $y$ і тепер продовжити процедуру з кроку $1$, але тепер ми будемо видаляти вже число $y$ з множини $X_{j+1}$.

Проаналізуємо часову складність процедури видалення. Скільки разів ми будемо попадати у випадок $2.2$? Нескладно зрозуміти, що не більше $m$ разів, оскільки кожен раз коли повертаємося на крок $1$, то розмір нашого поточного базису $X_j$ зменшується хоча б на $1$.

Кроки $2.1-2.2$ можна робити в лоб за $O(m^2)$:

1. Повністю перебудуємо XOR базис $X_j$ видаливши з нього елемент $v$ за $O(m^2)$;

2. Додаємо елементи одного базису $X_{j+1}$ в $X_j\setminus \{v\}$ за $O(m^2)$, щоб знайти $y$ або впевнитися, що такого немає.

Оскільки ці кроки можемо робити в гіршому випадку $m$ разів, то видалення буде працювати за $O(m^3)$.

Насправді кроки $2.1-2.2$ можемо робити за $O(m)$.

Перед тим як перейти до оптимізації, розглянемо як саме ми представляємо XOR базиси $X_i$, щоб з ними ефективно працювати.

Нехай $A$ та $B$ — XOR базиси, що побудовані алгоритмом вище. XOR базис, що представлений у такому вигляді має декілька важливих властивостей та наслідків з неї:

Розглянемо як саме видаляти число $v$ з базису та перебудовувати його за $O(m)$:

1. Кожне число базису також має маску $mask$, яка позначає лінійну комбінацію початкових елементів базису, за допомогою яких ми отримали цей елемент базису $val$.

2. Нам треба зробити так, щоб числа $v$ вже не було у лінійних комбінаціях та при чому базис залишився правильно побудованим (збереглася властивість, яку наводили вище).

3. Виявляється, що це зробити досить просто. А саме знаходимо таке число базису $x$, що містить $v$ у лінійній комбінації та серед таких чисел має найменший старший біт.

4. Далі видаляємо це знайдене число з базису та модифікуємо інші числа базису, що містили $v$ у лінійній комбінації, проXOR-ривши відповідне число з $x$. Таким чином старший біт у цих числах не зміниться, отже, і властивість збережеться.

5. Паралельно рахуємо число $bits$, що містить всі старші біти чисел базису, які містили у лінійній комбінації число $v$.

int rebuild_and_delete (int id) {
    int pos = 0, mn = inf, p2 = 0;
    for (int i = 0; i < basis.size(); i++) {
        if (basis[i].id == id) {
            pos = i;
        }
    }
    int bits = 0;
    for (int i = 0; i < basis.size(); i++) {
        if (basis[i].mask & (1 << pos)) {
            if (mn > basis[i].high) {
                mn = basis[i].high;
                p2 = i;
            }
            bits ^= 1 << basis[i].high;
        }
    }

    if (p2 != pos) {
        swap(basis[p2].id, basis[pos].id);
        for (auto &i : basis) {
            swap_bits(i.mask, pos, p2); // just swaps pos-th and p2-th bit in i.mask
        }
        pos = p2;
    }
    for (int i = 0; i < basis.size(); i++) {
        if (i != pos) {
            if (basis[i].mask & (1 << pos)) {
                basis[i].val ^= basis[pos].val;
                basis[i].mask ^= basis[pos].mask;
            }
        }
    }
    int good = (1 << pos) - 1;
    int other = ((1 << len(basis)) - 1) ^ (good | (1 << pos));
    basis.erase(basis.begin() + pos);
    for (auto &i : basis) {
        i.mask = ((i.mask & other) >> 1) | (i.mask & good);
    }
    return bits;
}

Далі треба знайти $y$ з твердження $1$ за $O(m)$ або сказати, що його не існує. Для $y$ має виконуватись така умова: $\mathrm{span}((X_j\setminus \{v\})\cup y)=\mathrm{span}(X_j)$. Ми знаємо який старший біт зник, при видаленні числа $v$ з $X_j$. Тому при додавання $y\in X_{j+1}$ до $X_j\setminus \{v\}$, $y$ має «відповідати» саме за цей зниклий біт.

Тоді можемо за для кожного $x\in X_{j+1}$ за $O(1)$ перевірити чи підходить воно в якості $y$. Нескладно переконатися, що $x$ підходить тоді та тільки, коли $\mathrm{cnt}(bits\&x)\mathrm{mod}2=1$, де $\mathrm{cnt}(t)$ — функція, що повертає кількість одиничних бітів у числі.

int get_the_same_high_bit (int bits, vector <int> &val) {
    for (auto &i : basis) {
        if (__builtin_popcount(val[i.id] & bits) & 1) {
            return i.id;
        }
    }
    return -1;
}

Тоді ми навчилися видаляти за $O(m^2)$.

З повною версією кода можна ознайомитись тут:

P. S. Подібно до додавання, ми можемо спробувати використати бінарний пошук для видалення: знайти максимальне $r$, що $\mathrm{span}(X_j\setminus \{v\})⊉\mathrm{span}(X_r)$. Але після переміщення цілого числа від $X_r$ до $X_j$ властивість послідовності базисів все ще може не виконуватися. І тому використання бінарного пошуку не покращує часову складність.

Деякий час я думав, що ми можемо зробити краще, ніж $O(m^2)$, але не вдалося покращити. Справа в тому, що за допомогою цієї властивості $\mathrm{span}(X_i)\supseteq \mathrm{span}(X_{i+1})$ ми можемо побудувати послідовність цілих чисел $a_i$ так, що $\mathrm{span}(X_i)=\mathrm{span}(\{a_1,a_2,\dots ,a_{\dim (X_i)}\})$ для всіх $i$. Маючи її, ми фактично можемо додавати за $O(m)$, але все ще не можу зрозуміти, як оптимізувати видалення.