定义
百度是这样说的
基：在线性代数中，基（也称为基底）是描述、刻画向量空间的基本工具。向量空间的基是它的一个特殊的子集，基的元素称为基向量。向量空间中任意一个元素，都可以唯一地表示成基向量的线性组合。如果基中元素个数有限，就称向量空间为有限维向量空间，将元素的个数称作向量空间的维数。
同样的，线性基是一种特殊的基，它通常会在异或运算中出现，它的意义是：通过原集合S的某一个最小子集S1使得S1内元素相互异或得到的值域与原集合S相互异或得到的值域相同。
简而言之是这样的
设数集 S 的值域范围为[1,2n−1], T 是 S 的线性基
T={t1,t2,t3,...,tn}（ tx 的最高位的 1 在第 x 位）
T 中元素互相异或所形成的集合，等价于原数集 S 的元素互相异或形成的集合
简单点，可以理解为将原数集进行了压缩
性质
- 线性基没有异或和为0的子集。
- 线性基的异或集合中每个元素的异或方案唯一，与性质1是等价。
- 线性基中元素互相异能得到原集合相互异或得到的值。
- 线性基是满足性质3的最小集合。
- 线性基二进制最高位互不相同。
- 如果线性基是满的，它的异或集合为[1,2n−1]。
原理
比如说现有集合A,B,A={x,y},B={x,x^y}
显然，A中元素所能异或得到的数形成的集合与B中元素所能异或得到的数形成的集合相同
那么我们把它扩展一下，假设现在有一个集合A，
新加进来一个数a，那么a与A中某个数异或一下得到A’，A’异或形成的集合肯定与A异或形成的集合相同
操作
维护
插入
设一个数的M值为他二进制上第一个1出现的位置
在这里，t[i]表示目前线性基中M值为i的这个数是多少
我们每次往线性基中插入一个数，都要让这个数的M值与之前线性基中的每一个数的M值都不同
每当我们新插入一个数x
我们从大到小枚举x的每一个二进制位
如果当前位置i上为1，那么x有可能对这个t[i]有贡献
我们查看t[i]是否已经有值,若t[i]==0，那么t[i]=x，否则x^=t[i]
通过我们前面的原理，这样显然是对的，而且这样我们在扫后面的位置时，保证出现的1就是第一个出现的
例：
t[3]=101
t[2]=0
插入110，在经过i=3时，110–>11
所以插入t[2]的时候M值已经为2了
void ins(ll x)
{
fd(i,62,0)
if((x>>i)&1)
{
if(!t[i])
{
t[i]=x;
break;
}
x^=t[i];
}
}
单次插入时间复杂度 O(logn)
合并
将一个线性基暴力插入另一个线性基
xxj merge(const xxj &n1,const xxj &n2)
{
xxj ans=n1;
fd(i,62,0) if(n2.t[i]) ans.ins(n2.t[i]);
return ans;
}
单次合并时间复杂度 O(log2n)
删除
据说不加特技的线性基不支持删除操作……
查询
存在性
如果无法插入就是存在了嘛
最大值
从高位到低位扫描线性基
如果异或后可以使得答案变大，就异或到答案中去
ll ask_max()
{
ll mx=0;
fd(i,62,0) mx=max(mx,mx^t[i]);
return mx;
}
x xor v的最大值
把mx的初始值改成v就行了
最小值
找到最小的i，使得t[i]!=0，那么t[i]就是答案
ll ask_min()
{
fo(i,0,62) if(t[i]) return t[i];
return 0;
}
第k小值
乍一看，一般的线性基好像不可做
问题在哪儿？
1000001
0000001
同时选1和2比只选1要小，所以我们无法做
但是如果线性基长成这样
1000000
0100000
0010000
0001000
0000100
那么就好做了，因为选取1和2一定比只选1要大。
所以我么需要对原来的线性基rebuild一下，使得它变成上面那样的形式，当然
1000010
0100001
0000101
这种形式也是可以的，因为同时选2和3也比只选2大
所以我们要使得若t[i]!=0，那么线性基里其他的数第i位上都为0
所以我们只需要拿t[i]去异或一下那些数就好了
rebuild之后的把k转成二进制，若k的第i位为1，那么将ans异或上rebuild后第i大的线性基
void rebuild()
{
fd(i,62,0)
fd(j,i-1,0)
if((t[i]>>j)&1) t[i]^=t[j];
fo(i,0,62) if(t[i]) p[cnt++]=t[i];
}
ll kth(ll k)
{
ll ans=0;
if(k>=1ll<<cnt) return -1;
fd(i,62,0) if(k&(1ll<<i)) ans^=p[i];
return ans;
}
模板
struct xxj
{
int cnt;
ll t[63],p[63];
xxj()
{
memset(t,0,sizeof(t));
memset(p,0,sizeof(p));
cnt=0;
}
void ins(ll x)
{
fd(i,62,0)
if((x>>i)&1)
{
if(!t[i])
{
t[i]=x;
break;
}
x^=t[i];
}
}
ll ask_max()
{
ll mx=0;
fd(i,62,0) mx=max(mx,mx^t[i]);
return mx;
}
ll ask_min()
{
fo(i,0,62) if(t[i]) return t[i];
return 0;
}
void rebuild()
{
fd(i,62,0)
fd(j,i-1,0)
if((t[i]>>j)&1) t[i]^=t[j];
fo(i,0,62) if(t[i]) p[cnt++]=t[i];
}
ll kth(ll k)
{
ll ans=0;
if(k>=1ll<<cnt) return -1;
fd(i,62,0) if(k&(1ll<<i)) ans^=p[i];
return ans;
}
}a1,a2;
xxj merge(const xxj &n1,const xxj &n2)
{
xxj ans=n1;
fd(i,62,0) if(n2.t[i]) ans.ins(n2.t[i]);
return ans;
}
参考文献
https://blog.csdn.net/qq_36056315/article/details/79819714
https://blog.csdn.net/qaq__qaq/article/details/53812883
https://www.cnblogs.com/vb4896/p/6149022.html
http://www.cnblogs.com/ljh2000-jump/p/5869991.html
https://blog.sengxian.com/algorithms/linear-basis