前言
线性基真的是一个非常神奇的算法。
它可以用于求解一个集合内的最大异或和，而且效率极高，是(O(N log MaxNum))的时间复杂度。
所以，它还是十分值得一学的。
关于线性基的定义
什么是线性基？
对于一个数组(a_1a_2...a_n)，我们可以用(num_1num_2...num_{log max(a_i)})来记录第一个二进制下最高位出现在第(i)位的数字。
并通过这个(num)数组，来求出这个数组中的最大异或和。
具体构造方式
关于线性基的构造，其实也是十分巧妙的。
我们先找到当前插入的数(x)二进制下的最高位(i)，然后对此时(num_i)是否为(0)进行分类讨论：
- (num_i=0)。说明这一位上还没有元素，所以令(num_i=x)。
- (num_i≠0)。说明这一位上有元素了，则我们令(x)^(=num_i)，从而将这一位消去，然后继续寻找(x)的最高位，重复以上过程。
由于(x)的最高位肯定是递减的，所以单次时间复杂度是(O(log_{a_i}))的，总复杂度是(O(N log max(a_i)))的。
询问最大异或和
关于如何询问最大异或和，其实也是很简单的。
我们从高位到低位枚举每一个(p_i)，并用(ans)记录答案。
对于当前(p_i)，我们有一个贪心的策略：若(ans)^(num_i>ans)，则更新(ans)为(ans)^(num_i)，否则就跳过。
这样贪心乍一看仿佛漏洞百出，实际上仔细一想还是有一定道理的。
为什么这样贪心一定是对的呢？
首先我们要知道一个最简单的性质：对于(num_i)，如果它不为(0)，则它二进制下最高位一定是第(i)位。
关于这一点的证明，可以结合上文线性基的定义与构造方式，这里就不予证明了。
则不难想到，(ans)^(num_i)后被影响到的肯定是后(i)位，且第(i)位肯定是发生变化的。
所以，如果(ans)^(num_i>ans)，我们就可以得到：原(ans)二进制下第(i)位为(0)，异或后的(ans)二进制下第(i)位为(1)。
由于后续操作是不会影响到第(i)位及前面已操作位的大小的，所以第(i)位肯定越大越优。
于是就可以通过贪心来求解了。
关于为什么(ans)^(num_ile ans)就跳过不再处理，其实也是同理的。
其他操作
除了这两个比较基础的操作，其实线性基还是有很多用途的，如：
- 查询是否有某些数异或和为(k)。
- 查询第(k)小值。
关于这些操作，我也只是听说过，因此这里就不介绍了。
代码
以【洛谷3812】【模板】线性基这道模板题为例，贴一份代码：
#include<bits/stdc++.h>
#define N 50
#define LL long long
using namespace std;
int n;
class FIO
{
private:
#define Fsize 100000
#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,Fsize,stdin),A==B)?EOF:*A++)
#define pc(ch) (void)(putchar(ch))
int Top;char ch,*A,*B,Fin[Fsize],Stack[Fsize];
public:
FIO() {A=B=Fin;}
inline void read(int &x) {x=0;while(!isdigit(ch=tc()));while(x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));}
inline void read(LL &x) {x=0;while(!isdigit(ch=tc()));while(x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));}
inline void write(LL x) {if(!x) return pc('0');while(x) Stack[++Top]=x%10+48,x/=10;while(Top) pc(Stack[Top--]);}
}F;
class Class_LinearBasis//线性基模板
{
private:
#define LogMax 50
LL num[LogMax+5];
public:
inline void Insert(LL x)//插入
{
for(register int i=LogMax;~i;--i)
{
if(!(x&(1LL<<i))) continue;//如果x第i位上值为0，跳过
if(num[i]) x^=num[i];else return (void)(num[i]=x);//如果这一位上没有值，就令num[i]=x；否则，令x^=num[i]
}
}
inline LL QueryMax(register LL ans=0)//查询最大异或和
{
for(register int i=LogMax;~i;--i) if((ans^num[i])>ans) ans^=num[i];//对于每一个num[i]贪心决定选与不选
return ans;//返回答案
}
}LinearBasis;
int main()
{
register int i;register LL x;
for(F.read(n),i=1;i<=n;++i) F.read(x),LinearBasis.Insert(x);
return F.write(LinearBasis.QueryMax()),0;
}