前言

这些东西有助于你了解线性基。

线性基是一种简洁有效的数据结构，一般用于解决异或和/最大值/第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. 若 能被线性基集合中的某个子集的异或和得到，该子集唯一。

2. 线性基集合中任意一个子集的异或和不为 。

3. 线性基集合中每个元素的最高位互不相同。

4. 若线性基集合中存在最高位为 的数，它的异或集合为 。

这些性质都较显然，结合定义和构造方法即可理解。

线性基的操作

用 数组存储线性基的元素。

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. 查询第 小

这时一般线性基就原地爆炸了。
为什么？
因为对于一个这样

101
001

的线性基，选第一个和第二个比只选第一个差。

那么如果这个线性基可以变成这个样子，

100
001

选第一个和第二个比只选第一个优，就变得可做了。
所以我们只需要对于 且 的第 位为真的 做 操作，即可使第一种线性基转变为第二种线性基。

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 最后一题，题目链接。读者不妨自行思考。

另外，亦可思考其与高斯消元法的联系。

结语

本文因作者才疏学浅，难免有不足之处。若有任何问题，希望大家不吝赐教。
看了这么多，点个赞或收藏下再走吧。