线性基

基：在线性代数中，基（也称为基底）是描述、刻画向量空间的基本工具。向量空间的基是它的一个特殊的子集，基的元素称为基向量。向量空间中任意一个元素，都可以唯一地表示成基向量的线性组合。如果基中元素个数有限，就称向量空间为有限维向量空间，将元素的个数称作向量空间的维数。
同样的，线性基是一种特殊的基，它通常会在异或运算中出现，它的意义是：通过原集合S的某一个最小子集S1使得S1内元素相互异或得到的值域与原集合S相互异或得到的值域相同。

上文来自百度百科。

线性基中的“基”

个人理解，线性基的“线性”表示的是数列，即用一个数列表示另一个数列。而“基”表示的是一种类似于向量的思想。因为原数列中的每个数都是不同的，那么它们每个数就分别对应一些线性基的异或和——和向量的表示方式有异曲同工之处。

大概理解了思想后，我们来理解它的构造。线性基是一个数列，其大小为原数列的最大数的二进制位数（所以是longlong的话大概最好开65位）。它的每一位是原数列中的一个数。有可能含有多个零。

线性基的性质

1. 可以用线性基中任意个数异或和表示原数列中的所有数（或者说是原数列中任意数的异或和，表达其实是等价的）
2. 线性基中的任意数的异或和不可能为0（除非你用0异或0，然而并不算做线性基内部的数）
3. 线性基是满足性质1的最小集合

俺不会证明XD

线性基的构造

每插入一个数，我们从最高位向下遍历（注意这里是指二进制位数），找到第一个线性基上没有的插入并跳出，如果已经有数则与之异或（保证线性基的所有性质）：
inline void insert(ll x){ for(ll i=62;i+1;i--){ if(!(x>>i))continue; if(!p[i]){ p[i]=x; break; } x^=p[i]; } }

线性基的应用

查询异或和最小值

最小值就是p的最小的值啦~因为它任意异或一个比它大的线性基的数一定都比它大。

查询异或和最大值

既然能由任何数异或得到原数列任意异或和的值，我们再次从上向下遍历，每异或后的值大于原答案，就取这个值。
inline ll find(){ ll ans=0; for(ll i=63;i>=0;i--) if((ans^p[i])>ans) ans^=p[i]; return ans; }
说起来你可能不信：这玩意还支持删除！

线性基

原文：https://www.cnblogs.com/BrotherHood/p/13388071.html