这些东西有助于你了解线性基。线性基是一种简洁有效的数据结构，一般用于解决异或和/最大值/第K大等问题。常用的线性基一般是定义在模2意义下（大部分为异或空间）中的。本文旨在以不那么深奥的方式解释这个数据结构。这些东西有助于你理解线性基。1. 张成子空间（span）百度百科链接设 ，所有子集
的异或和组成的集合即为 张成的子空间，记作 。通俗解释就是在
中选任意多个数，所有可能的异或和组成的集合。异或空间下的定义即为用集合中的数可以异或出的数组成的集合。2. 向量空间（vector space）以下内容摘自百度百科 [1]。 向量空间亦称线性空间。它是线性代数的中心内容和基本概念之一。设V是一个非空集合，P是一个域。若： 1.在V中定义了一种运算，称为加法，即对V中任意两个元素α与β都按某一法则对应于V内惟一确定的一个元素α+β，称为α与β的和。 2.在P与V的元素间定义了一种运算，称为纯量乘法(亦称数量乘法)，即对V中任意元素α和P中任意元素k，都按某一法则对应V内惟一确定的一个元素kα，称为k与α的积。 3.加法与纯量乘法满足以下条件： 1) α+β=β+α，对任意α，β∈V. 2) α+(β+γ)=(α+β)+γ，对任意α，β，γ∈V. 3) 存在一个元素0∈V，对一切α∈V有α+0=α，元素0称为V的零元. 4) 对任一α∈V，都存在β∈V使α+β=0，β称为α的负元素，记为-α. 5) 对P中单位元1，有1α=α(α∈V). 6) 对任意k，l∈P，α∈V有(kl)α=k(lα). 7) 对任意k，l∈P，α∈V有(k+l)α=kα+lα. 8) 对任意k∈P，α，β∈V有k(α+β)=kα+kβ， 则称V为域P上的一个线性空间，或向量空间。V中元素称为向量，V的零元称为零向量，P称为线性空间的基域.当P是实数域时，V称为实线性空间.当P是复数域时，V称为复线性空间。例如，若V为三维几何空间中全体向量(有向线段)构成的集合，P为实数域R，则V关于向量加法(即平行四边形法则)和数与向量的乘法构成实数域R上的线性空间。又如，若V为数域P上全体m×n矩阵组成的集合 ，V的加法与纯量乘法分别为矩阵的加法和数与矩阵的乘法，则
是数域P上的线性空间.V中向量就是m×n矩阵。再如，域P上所有n元向量(a1，a2，…，an)构成的集合P对于加法：(a1，a2，…，an)+(b1，b2，…，bn)=(a1+b1，a2+b2，…，an+bn)与纯量乘法：λ(a1，a2，…，an)=(λa1，λa2，…，λan)构成域P上的线性空间，称为域P上n元向量空间。 简单讲就是一个包含向量加法和标量乘法（数乘运算）的封闭向量集合。若这个线性空间推广为一个异或空间，那么就是一个关于异或运算的封闭的集合，零元为
， 为非负整数域。3. 线性相关和线性无关（linearly dependent & linearly independent）对于一个线性空间中的若干个向量，如果存在一个向量可以被除它以外的向量标出，即称这些向量线性相关，否则称这些向量线性无关。异或空间下线性相（无）关即为（不）存在一个数可以被除它以外的数异或出。4. 线性基（linear basis）一个线性空间张成的线性无关子集被称为线性空间的基底，简称基。另一种基的定义方式是线性空间的极大线性无关子集。一个线性空间可以有多个基，但所有基内的向量个数（称为“维数”）都相等。举个小栗子：对于一个立体空间，它的所有向量构成一个三维线性空间。
就是它的一个基。另一个经典的例子就是二维平面直角坐标系。如图， 和
分别是坐标系的单位向量，即基向量。那么，将向量
反向拉升为原来的
倍，向量
拉升为原来的 3 倍，即可表示出一个新的向量 。同理，坐标系中的向量都可以通过缩放/加减基向量得到。基向量的选择也可以多种多样，如图：亦可表示出一些新的向量。5. 秩和拟阵（rank & matroid）秩·百度百科链接通俗地讲即是一个矩阵的行/列秩即是其线性独立的行/列的极大数。用初等行变换把原矩阵变换为阶梯型矩阵，非零的行数即为矩阵的秩。初等行变换（百度百科链接）即是 用一个非零的数乘某一方程；把某一方程的倍数加到另一个方程；互换两个方程的位置 三个操作的合称。这有个某帮上的栗子。对于矩阵：1 1 2 2 1
0 2 1 5 -1
2 0 3 -1 3
1 1 0 4 -1我们将其变换为：1 1 2 2 1
0 2 1 5 -1
0 0 0 0 0
0 0 1 -1 1故秩为 。拟阵·百度百科链接拟阵可以用于证明大部分贪心算法的正确性，而线性基有一个重要性质：用线性基解决的问题大多可以按位贪心。这条性质亦可以用拟阵来证明。可是我太菜了，不会证。而且同是 OIer 你要证什么明。关于拟阵证明贪心算法的基础学习可以参考：
刘桂真, 陈庆华. 拟阵[M]. 长沙: 国防科技大学出版社, 1994 呐，其实我们可以感（自）性（欺）理（欺）解（人）一下。异或运算只和当前位有关系，所以我们一定会要求最大位尽可能地大/小。不就是个贪心嘛。若
能被线性基集合中的某个子集的异或和得到，该子集唯一。
线性基集合中任意一个子集的异或和不为 。
线性基集合中每个元素的最高位互不相同。
若线性基集合中存在最高位为
的数，它的异或集合为 。
这些性质都较显然，结合定义和构造方法即可理解。用
数组存储线性基的元素。1. 插入 插入操作的本质就是在高斯消元。如果是预处理的话，将每个数二进制展开，将高斯消元的加法换为异或即可。同理，可得在线算法的过程：插入数
时：① 从高到低扫描它为
的二进制位。② 扫描到第
位时，如果
不存在，就令 ，否则 。③ 最后，
要么被插入线性基，要么变成 。bool Insert(int x)
{
for(int i=MAX_LIM;~i;i--)
if(x&(1<<i))
if(!p[i]) return p[i]=x,1;
else x^=p[i];
return 0;
}2. 查询最大值/最小值查询最大值时：从高到低扫描，对于
和
取最大值即可。int AskMax()
{
int res=0;
for(int i=MAX_LIM;~i;i--) res=max(res,res^p[i]);
return res;
}查询最小值时：取最小的一个存在的
即可。int AskMin()
{
for(int i=MAX_LIM;~i;i--)
if(p[i]) return p[i];
return 0;
}有一些题目可能会询问一个数
在线性基内可以异或出的最大值/最小值。此时只需将
的初始值改为
即可。3. 查询第
小这时一般线性基就原地爆炸了。为什么？因为对于一个这样 101001 的线性基，选第一个和第二个比只选第一个差。那么如果这个线性基可以变成这个样子， 100001 选第一个和第二个比只选第一个优，就变得可做了。所以我们只需要对于
且
的第
位为真的
做
操作，即可使第一种线性基转变为第二种线性基。int k0=0;
void Setup()
{
for(int i=MAX_LIM;~i;i--)
for(int j=i-1;~j;j--)
if(p[i]&(1<<j)) p[i]^=p[j];
for(int i=0;i<=MAX_LIM;i++)
if(p[i]) kt[k0++]=p[i];
}那么查询时只需对于
的每一位都异或
即可。但是，如果线性基可能构造出
，则需要给
减 。bool Insert(int x)
{
for(int i=MAX_LIM;~i;i--)
if(x&(1<<i))
if(!p[i]) return p[i]=x,1;
else x^=p[i];
return ri=1,0;
}
int Kth(int k)
{
k-=ri;
if(k>>k0) return -1;
int res=0;
for(int i=k0-1;~i;i--)
if(k&(1<<i)) res^=kt[i];
return res;
}4. 查询
的排名方法1：二分法时间复杂度 ，直接二分
是否等于
即可。int Binary_Search(int x)
{
int l=0,r=1<<MAX_LIM;
while(l<=r)
{
int mid=(l+r)>>1,tmp=Kth(mid);
if(tmp<x) l=mid+1;
else if(tmp>x) r=mid-1;
else return mid;
}
return -1;
}方法2：
法没有名字就乱取了个。顾名思义，套用查询第
小的
操作，同时开一个
存储当前累加的排名。注意此时
存的是第
个有值的
的下标，即 。从后往前扫
数组，如果
的第
位为真，则这一位为假时前面的
共
位随便怎么取都会比
小，所以
需要加上 。如果
最后 ，则线性基集合与
线性无关。是一个比较好理解的算法，若不理解可以手玩下面这组栗子：线性基数组p：
p[0]=1,p[1]=2,p[3]=0,p[4]=8
可以异或出的数：1,2,3,8,9,10,11
求10的排名。
10的第3位为真，那么所有第3位为假的数（0,1,2,3）都要被算入答案；
10的第1位为真，那么所有第1位为假（但第3位为真）的数（8,9）都要被算入答案。
特判0的情况，故10的排名为6。仍需特判能否构造出
的问题。下面的代码并没有考虑这个问题。int Rank(int x)
{
int res=0;
for(int i=k0-1;~i;i--)
if(x&(1<<kt[i])) res+=1<<i,x^=p[kt[i]];
return x?-1:res;
}5. 合并两个线性基暴力插入。void Merge(int *p1,int *p2)
{
for(int i=MAX_LIM;~i;i--)
if(p2[i]) Insert(p1,p2[i]);
}6. 线性基求交/并本质是线性空间求交/并。一道很有意思的题，为 Atcoder ZONe Energy Programming Contest 最后一题，题目链接。读者不妨自行思考。另外，亦可思考其与高斯消元法的联系。本文因作者才疏学浅，难免有不足之处。若有任何问题，希望大家不吝赐教。看了这么多，点个赞或收藏下再走吧。#学习路径#}