Base XOR con eliminaciones

Prólogo

Este artículo utiliza términos de álgebra lineal. Si los entiendes, puedes saltarte esta sección.

Introducción

Recordemos el siguiente problema conocido:

Puedes aprender más sobre cómo resolver este problema aquí.

En este artículo, consideraremos un problema más complejo donde también hay consultas de eliminación de números enteros del conjunto $S$. Además, recibimos la siguiente consulta solo después de responder la anterior (es decir, el problema necesita resolverse "en línea").

El problema inicial puede resolverse en $O(m)$ por consulta, pero aprenderemos a resolver el problema con eliminaciones en $O(m^2)$.

Estructura

En el problema con eliminaciones, surgen incertidumbres cuando el número entero que añadimos a la base XOR se puede representar mediante $\mathrm{xor}$ de los números ya existentes en la base.

Queremos almacenar de manera eficiente cada número que se añade a $S$, así que mantendremos una secuencia $X_n$ ($n\ge 1$) de bases XOR (cada una de las cuales está inicialmente vacía), en lugar de una sola base.

Añadir un número entero $v$ a $S$

Consideremos cómo añadiremos un nuevo número entero $v\ne 0$ al conjunto $S$:

1. Iteraremos gradualmente sobre nuestras bases comenzando desde la primera. Sea $i$ el número de la base actual que estamos considerando;

2. Si $v\notin \mathrm{span}(X_i)$, simplemente añadimos $v$ a $X_i$ y terminamos el procedimiento;

3. De lo contrario, $v\in \mathrm{span}(X_i)$, por lo que no podemos añadirlo a la base, pero queremos almacenar este número en algún lugar. Por lo tanto, incrementamos $i$ en $1$ y volvemos al paso $2$.

En otras palabras, encontramos el menor $i$ tal que $v\notin \mathrm{span}(X_i)$ y añadimos $v$ a $X_i$. Si implementamos este algoritmo directamente, en el peor caso funcionará en $O(|S|)$, lo cual es bastante ineficiente.

Mejoraremos este algoritmo. Primero, consideremos algunas propiedades de esta secuencia de bases $X_n$: