线性基 学习笔记
简介
线性基，是指n维空间的单位向量所构成的集合。由几何知识可以知道，n维空间的单位向量至多有n个，其余的向量都可以用这n个向量进行一些运算来得到，因此线性基的空间是线性的，由此得名“线性基”
构造
为了让线性基更好地支持一些查询，我们使得线性基中的向量满足：第i个向量的前i-1维均为0。这样做的好处在之后的高斯消元中会体现出来
于是可以运用高斯消元的思想构造线性基
对于一个给定的向量，我们用已有的基底向量对它进行高斯消元，若它最终变为0，则表明已有的基底向量可以运算得到它，因此它不需要加入线性基；若它最终没有变为0，那么就将它加入相应位的基中。
因为第i个向量的前i-1维均为0，所以高斯消元可以很好地支持这一过程
常见情形——异或线性基
简介
异或是信息学奥赛中常考的内容，线性基经常是以异或的形式作为考点考察的。常见的类型有：给定一些数，询问任取一些数的异或最大值、询问某个数能否被这些数异或出来
构造
与普通线性基相同，使用高斯消元的思想。
我们令第i个基满足其二进制的前i-1位均为0，于是可以得到这么一个大致算法：
枚举已有基，若x在某一位上为1，则进行操作：若这一位有基了，x异或上它然后继续；若这一位还没有基，那x就是这一位的基
“x异或上它”其实就是高斯消元的过程，相当于把这一位消去了
最大值询问
之前提到过字典树的妙用，可以求给定的数中任取两数的异或最大值。线性基解决的问题稍有不同，它解决的是给定数中任取一些数的异或最大值（注意：题目并未规定具体取多少，而是任取一些）
那么可以贪心地自高位向低位取值。因为低位的基中保证了高位为0，不会对高位取的的答案造成影响，故自高向低取的贪心是正确的
具体地，一开始设答案为0，然后自高位向低位枚举已有基，若答案异或上枚举到的基比之前的答案大，那答案就贪心地异或上这个基，最终就可以得到异或最大值
存在性询问
询问给定数能否被已有的数异或出来
显然地，还是因为低位的基高位为0，所以要想把高位异或出来，必须要有高位的基。
因此，从高位向低位枚举已有基，若x的相应位为1，则异或上这个基。若x最终可以变为0，则可以被异或出来；否则一定异或不出来
模板
下面是异或线性基三类操作的模板
int base[35];
void Insert(int x)
{
for(int i=30;i>=0;i--)
if(x&(1<<i))
{
if(base[i]) x^=base[i];
else{base[i]=x;break;}
}
}
int Max()
{
int ans=0;
for(int i=30;i>=0;i--)
if((ans^base[i])>ans) ans^=base[i];
return ans;
}
bool Exist(int x)
{
for(int i=30;i>=0;i--)
if(x&(1<<i)) x^=base[i];
return x==0;
}
浅谈线性基合并的优化
线性基的合并，是一个看上去比较暴力的操作，即把其中一个线性基里面的所有基，一个一个插入另一个线性基中
这样做的时间复杂度是两个log的，很容易被卡常，尤其是有时候和线段树一起用时，就是三个log了
那么一个重要的优化就是，假如我们把A暴插进B，我们只要将A中的非0基插过去即可。也就是加一个特判，假如这一位基是0，就不插
这个优化还不够，还可以再加一个
插入时做一个判断，假如我们要把A暴插进B，然后B又已经满了，就直接退出合并过程
加了这两个判断之后，多次合并的时间复杂度就期望是一个log了