线性基

定义

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

上文来自百度百科。

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

UPD 2024-8-14：实际上就是二进制异或基，不是异曲同工，就是一个曲儿。

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

线性基的性质

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

俺不会证明XD

UPD 2024-8-14：这就是“基”的定义，详见线性代数。

线性基的构造

每插入一个数，我们从最高位向下遍历（注意这里是指二进制位数），找到第一个线性基上没有的插入并跳出，如果已经有数则与之异或（保证线性基的所有性质）：

1
2
3
4
5
6
7
8
9
10

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的最小的值啦~因为它任意异或一个比它大的线性基的数一定都比它大。

查询异或和最大值

既然能由任何数异或得到原数列任意异或和的值，我们再次从上向下遍历，每异或后的值大于原答案，就取这个值。

1
2
3
4
5
6
7

inline ll find(){
	ll ans=0;
	for(ll i=63;i>=0;i--)
		if((ans^p[i])>ans)
			ans^=p[i];
	return ans;
}

其他

• 保存历史信息可以做到删除。
• 基的大小只有 \(O(\log n)\)，可以用该性质处理问题，比如用线段树维护线性基。