学术：浅谈线性基

引言
- 线性基是什么？
第一部分：线性代数基础知识
- 2.1 向量空间（Vector Space）
- 2.2 线性组合（Linear Combination）与线性张成（Linear Span）
- 2.3 线性相关（Linearly Dependent）与线性无关（Linearly Independent）
- 2.4 基（Basis）与维数（Dimension）
- 2.5 基的核心性质
第二部分：异或线性基
- 3.1 异或运算下的向量空间
- 3.2 线性基的构造（插入操作）
  - 算法流程
  - 正确性理解：高斯消元的视角
  - 构造过程实例
- 3.3 线性基的性质
  - 基向量的“三角化”特征
  - 张成空间不变性
  - 表示的唯一性
  - 基的大小与原集合的秩
- 3.4 线性基的“标准化”处理
  - 为何需要标准化
  - 标准化过程（类高斯-约旦消元）
第三部分：经典问题应用
- 4.1 查询最大异或和
  - 正确性证明
- 4.2 查询最小异或和
- 4.3 查询第 k 小异或和
  - 基于标准化基的解决方案
  - 处理异或和为 0 的情况
- 4.4 判断一个数能否被表示
- 4.5 合并两个线性基
第四部分：代码实现
第五部分：进阶话题与扩展
- 6.1 线性基与图论结合：路径异或和问题
- 6.2 区间线性基
- 6.3 带删除的线性基
- 6.4 线性基与高斯消元的等价性
第六部分：不止异或线性基
总结

1. 引言

线性基是什么？

异或，基础位运算之一，其特殊的非线性性质，在很多场景下又有用，又难以处理。然而在 OI 中特殊的论域之下，线性基作为一个强势的工具，可以高效解决很多关于集合上的异或问题。

从 OI 角度看，线性基是一个数据结构，它维护了一个数字集合，并能高效地回答与该集合的“异或张成空间”相关的问题。

从线性代数的角度看，线性基是某个向量空间的一组基，所有重要的性质和定理都能够使用。

一个由数字和异或运算构成的系统，完美地符合线性代数中“向量空间”的定义。这使得我们能够运用线性代数中关于“基”的理论来分析和解决这些复杂问题。

“基”，就是基础、精髓，作为一个极小的、性质优良的集合，却能等价地表示一个可能非常庞大的原始数字集合的全部异或可能性。

2. 线性代数基础知识

2.1 向量空间（Vector Space）

向量空间是一个由向量和标量组成的系统，它满足一系列特定的公理。

向量（Vectors）：几何向量，多项式，函数，甚至数字的二进制表示都可以是向量，只要满足八条规则即可。
标量（Scalars）：通常是实数或复数。异或线性基论域下，标量作为二进制位上的数字，只有两个：0 和 1。
两个核心运算：
1. 向量加法：两个向量相加得到另一个向量。
2. 标量乘法：一个标量乘以一个向量得到另一个向量。

简单来说，一个向量空间就是一个集合，集合内的元素可以自由地进行加法和标量乘法，且结果仍然在这个集合内。

2.2 线性组合（Linear Combination）与线性张成（Linear Span）

线性组合，囊括了几乎所有线性代数中的计算，它是向量加法和标量乘法的结合形式，是最宽泛的向量之间的运算的称呼。

给定一组向量和一组标量，表达式

被称为向量组的一个线性组合。

向量组 张成的空间（Span），记作，是所有可能的线性组合得到的结果的集合。换句话说，包含了所有能够被中向量“表示”出来的向量。

例子：

在二维平面上，向量和张成的空间是整个二维平面，因为任何向量都可以表示为。
而向量和张成的空间只是一条 x 轴，因为它们的任何线性组合的 y 分量永远是 0。

2.3 线性相关（Linearly Dependent）与线性无关（Linearly Independent）

感性解释

我们讨论的是基，希望这个集合能够以最精简的姿态发挥最强大的功能，这意味着我们必须剔除所有的冗余。

以平面直角坐标系为例，其中有这两个基向量，所谓向量的坐标表示，所谓看作一个点，本质上是对基向量的线性组合的简写：

由于平面直角坐标系中每个点都是可表示的，所以如果我们想要描述二维的空间，那么这一对足够了，不需要添加更多的向量，因为其他的都可以被这一对表示，那就形成了冗余。这时，我们称向量组线性相关，而线性无关。

形式化定义

对于一组向量，如果存在不全为零的标量使得：

那么我们称这个向量组是线性相关的。这意味着这组向量中至少有一个向量是多余的，它可以被其他向量线性表示出来。例如，如果，我们就可以移项得到：

反之，如果使得上述等式成立的唯一一组标量是，那么我们称这个向量组是线性无关的。此时这组向量中每一个向量都是不可或缺的，它们各自贡献了“新的方向”，无法被其他向量组合出来。

是线性相关的，因为。
是线性相关的，因为。

2.4 基（Basis）与维数（Dimension）

一个向量空间的一组基（Basis）是的一个子集，它同时满足以下两个条件：

线性无关：中的向量是线性无关的。
张成空间：，即中的任何一个向量都可以由中的向量线性组合而成。

基可以被看作是描述整个向量空间的最简化的、无冗余的坐标系。

线性无关保证了基中没有多余的向量，是“最简”的。
张成空间保证了基能够覆盖整个空间，是“完备”的。

一个向量空间可以有很多组不同的基，但所有基的元素个数都是相同的。这个数字被称为该向量空间的维数（Dimension）。

2.5 基的核心性质

唯一表示性：对于一个给定的基，空间中的任何一个向量都可以被唯一地表示为。这组唯一的标量就是在这组基下的坐标。
极大线性无关组：一个基是向量空间中的一个极大线性无关组。也就是说，你不能再往基里添加任何一个空间中的向量而不破坏其线性无关性。
极小生成组：一个基是向量空间中的一个极小生成组（张成集合）。也就是说，你从基里移除任何一个向量，它都将无法张成整个空间。

3. 第二部分：异或线性基

3.1 异或运算下的向量空间

我们可以构建一个向量空间：

向量：每个非负整数对应一个向量。这个向量可以看作是的二进制表示，例如，数字 13 是一个向量。
标量域：。
向量加法：定义为两个数字的异或运算。例如，就是。
标量乘法：

这个系统满足向量空间的所有公理。例如，加法结合律，加法单位元是 0 ()，每个元素的逆元是其自身 ()。

在异或向量空间里：

线性组合：。由于标量只能是 0 或 1，就等价于从向量组中选取一个子集求异或和。
线性张成空间：原数字集合的张成空间，就是从中任取若干个数进行异或，所有可能得到的结果的集合。
线性无关：一组数是线性无关的，当且仅当不存在它们的非空子集的异或和为 0。

OI 中线性基的目标：对于给定的数字集合，找到一组基，使得。这组基就是我们所说的的线性基。

3.2 线性基的构造（插入操作）

线性基中存储一个特殊的数字，其二进制下的最高位是第位。如果，则表示这个“维度”的基向量还不存在。

注意，有些同学误以为数组中每个位置存储一个 0/1，这是不对的。

线性基是一个向量的集合，里面的每一个元素是一个向量，而每一个 0/1 则是向量的某个维度上的值。

算法流程 insert(x):

从最高位开始向下遍历，比如从到。
检查的第位是否为 1。
如果的第位是 1：
- ，则为新的线性无关的向量，它负责张成维度。直接令，然后结束插入过程。
- ，说明维度已经有基向量负责了。为了消除在第位的“分量”，我们令。然后继续循环，用新的去尝试更低的位。这保证了仅仅是在原有基上的扩展，并且原有是可以被表示的。
如果循环结束，说明与当前基是线性相关，此时做一些题目要求的特殊处理。

高斯消元的视角

插入过程本质上就是在对一个矩阵进行高斯消元。

我们把所有数字二进制拆分写成向量，逐行堆叠形成一个矩阵。这个矩阵没有方程组意义，因为不具有增广部分。但是由于基的性质，目标就是让行第一个出现在列，也就是把左下角的三角形清零。

当我们插入一个新数 (新的一行)时，我们从高位向低位扫描。
（第列的主元行），我们就用这一行去消掉的第位。但同时为了原的可行性，我们选择操作时对于整个向量进行异或。
如果不存在，说明在第列提供了一个新的主元。我们就把放在这里，作为第列的主元行，即。

最终，数组里存储的就是一个行阶梯形矩阵，每一行是一个基向量。

构造过程实例

对集合构造线性基：

初始化线性基。

插入 3 ():
- ，跳过。
- 。插入结束。
- 当前基: 。
插入 5 ():
- 。插入结束。
- 当前基: 。
插入 6 ():
- 。
- 。
- 现在变成了 0。循环结束。说明 6 可以被表示（）。
- 最终基: 。

所以，的一个线性基是。。

3.3 线性基的性质

通过上述方法构造出的线性基具有一些非常优美的性质：

基向量的“三角化”特征：是行阶梯形矩阵，左下三角形为空。
张成空间不变性：任何能被中元素异或出的数，也一定能被中元素异或出来，反之亦然。这是因为插入过程中的操作是可逆的等价变换，没有改变空间的本质。
表示的唯一性：对于中的任何一个非零数，它被中元素异或出的方式是唯一的。
- 证明：假设有两种表示方法，，其中都是基向量。那么。这与基向量是线性无关的定义相矛盾。
基的大小与原集合的秩：线性基中非零元素的个数，就是原集合的秩（rank），也等于其张成空间的维数。

3.4 线性基的“标准化”处理

我们上面构造的线性基是一个“三角基”，类似于高斯消元得到的行阶梯形矩阵。但有时，为了解决某些问题（如求第 k 小），我们需要一个性质更好的基，它类似于高斯-约旦消元得到的最简行阶梯形矩阵（Reduced Row Echelon Form）。

正如平面直角坐标系中，虽然可以为一组基，但是大家都喜欢用，因为它纯粹、正交。

所以有一个标准化的线性基，除了满足的最高位是之外，还要求的二进制表示中，除了第位，其他为 1 的位，都满足 。换句话说，的第位为 1，当且仅当或者不存在。最后长成这样：

标准化过程：

在构造完三角基之后：

。
如果不为 0：
- 。
- 如果的第位为 1，则令。

就是用低位的基向量去消除高位基向量在第位的分量。正确性显然。

4. 第三部分：经典问题应用

4.1 查询最大异或和

对集合构造线性基，从高位到低位遍历：

正确性证明：

，由于线性基的三角性质，该操作不会影响比更高的位，因此，异或上肯定会使结果变大。
这个逻辑等价于，是一个更简洁、被大家认可的写法。

4.2 查询最小异或和

解法：

对集合构造线性基，分类讨论：

是线性相关的，可在插入是判断，答案为。
是线性无关的，答案就是。因为所有异或的类型我们都尝试过了，冗余的没有出现，而最小的是不会被冗余掉的。

4.3 查询第 k 小异或和

问题：给定一个集合，求其所有子集异或和中，第小的值是多少（去重后）。

解法：

构造线性基，并记录基的大小，并对线性基进行标准化处理，使得基向量之间“正交”。
将标准化后的基中所有非零元素从大到小拿出来，形成一个数组，大小为。
特判线性相关的情况，此时 k--，则问题为求第小的非零异或和。
$k = (c_{d-1} c_{d-2} … c_1 c_0)2 $，则如果$ k $的第$ i $位是，就把$ b[i] $异或到答案中：$ $ ans = (c_0 \cdot b_0) \oplus (c_1 \cdot b_1) \oplus \dots \oplus (c{d-1} \cdot b_{d-1}) $$

为什么这个方法正确？

从小到大且在每一位独一无二，选取其中的进行异或只会更大不会更小；
从小到大选取共有中选择，其结果的大小顺序正好对应于的二进制拆分；

4.4 判断一个数能否被表示

解法：

和 insert 几乎完全一致，就是判断当前数是否与基线性相关，也就是是否能够撑到循环结束。

4.5 合并两个线性基

问题：有两个集合和，以及它们各自的线性基和。求的线性基。

解法：

最简单直接的方法是暴力合并，把中的挨个插入。

这个方法的复杂度是，其中是数值范围。因为中有个元素，每次插入的复杂度是。如果想要进一步优化，可以考虑按秩合并。

5. 第四部分：代码实现

下面是一个较为完整的 C++ 线性基模板，包含了上述所有核心功能。

struct LinearBasis {
    int dim;
    bool dep;
    vector<LL> bas;

    inline void resize(int siz) {
        bas.resize(siz + 1, 0);
        dep = false;
        dim = siz;
        return;
    }
    inline void reset() {
        fill(bas.begin(), bas.end(), 0);
        dep = false;
        return;
    }
    inline void stdize() {
        for (int i = 0; i <= dim; ++i) {
            if (!bas[i])
                continue;
            for (int j = dim; j > i; --j)
                if (bas[j] & (1LL << i))
                    bas[j] ^= bas[i];
        }
        return;
    }
    inline LinearBasis merge(const LinearBasis& another) const {
        LinearBasis res = *this;
        res.dep |= another.dep;
        for (int i = 0; i <= another.dim; ++i)
            if (another.bas[i])
                res.insert(another.bas[i]);
        return res;
    }

    inline void insert(LL val) {
        for (int i = dim; i >= 0; --i)
            if (val & (1LL << i)) {
                if (!bas[i])
                    return bas[i] = val, void();
                val ^= bas[i];
            }
        dep = true;
        return;
    }
    inline bool check(LL val) {
        for (int i = dim; i >= 0; --i)
            if (val & (1LL << i)) {
                if (!bas[i])
                    return false;
                val ^= bas[i];
            }
        return val == 0;
    }

    inline LL queryMax() {
        LL res = 0;
        for (int i = dim; i >= 0; --i)
            if (bas[i])
                res = max(res, res ^ bas[i]);
        return res;
    }
    inline LL queryMin() {
        if (dep)
            return 0;
        for (int i = 0; i <= dim; ++i)
            if (bas[i])
                return bas[i];
        return 0;
    }

    inline LL queryKth(LL k) {
        if (dep)	k--;
        if (k == 0) return 0;

        vector<LL> tmp;
        for (int i = 0; i <= dim; ++i)
            if (bas[i])
                tmp.push_back(bas[i]);
        LL res = 0, siz = tmp.size();
        for (int i = 0; i < siz; ++i)
            if (k & (1LL << i))
                res ^= tmp[i];
        return res;
    }
};

6. 第五部分：进阶话题与扩展

线性基的应用远不止于此，它可以和各种数据结构结合，解决更复杂的问题。

6.1 线性基与图论结合：路径异或和问题

经典问题：给定一张带边权的无向图，查询从点到点的所有路径中，路径异或和最大/第K小是多少。

核心思想：
任意一条到的路径，其异或和可以被拆解为： 到的一条任意简单路径的异或和图中若干个环的异或和。

证明：
考虑对两条从到的路径和进行异或，其中公共边被异或两次，结果为0，抵消了。剩下的边恰好构成图中的一个或多个环。所以 $一些环的异或和$ ，移项得 $一些环的异或和$ 。

算法步骤：

在图上构建一棵生成树，并计算出根节点到其他所有点的路径异或和。
找出图中所有的基本环。对于一条非树边，其权值为，则环到的异或和是。
将所有基本环的异或和插入一个线性基。这个线性基张成了图中所有环路构成的异或空间。
查询从到的路径异或和问题：

首先，任选一条到的简单路径。最方便的就是树上路径，其异或和为。
问题转化为：求 $线性基中的某个值$ 的最大/第K小值。
求最大值：将作为初始值，在线性基上跑。
求第K小：需要先求出线性基能表示出的第 K 小值，然后答案就是。（注意这里的K小不是全局的，而是以为基准的）。

理解 1：有关基本环

基本环，顾名思义，是由一条非树边和两端的树上路径组成的环。也就是说，我们插入的环都只有一条非树边；
当我们把基本环异或起来的时候，他们重复的树边就被消掉了，正好无缝衔接出了一个大环，这就是“基本”的意思，也是“线性基”中“基”的意思；
也就是说，我们插入基本环，它们张成的空间就是树上的所有环路；

理解 2：所有环

当我们把所有的基本环都纳入考虑的时候，那有的同学就要问了：

欸，有的环和树上的路径毫不相关，比如在树上的另一端，为什么我们还要进行考虑？

也就是说，我们出现了一个情况，我们走到环上的路径是唯一的（不然就是一个相关的大环了），我们走过去，走回来，异或值为零，恰好等同于仅考虑环和原有路径的情况。这么走只有环产能生了贡献。

6.2 区间线性基

问题：给定一个序列，支持区间查询最大异或和，或支持单点修改。

解法：

单点修改、区间查询：可以用线段树来解决。线段树的每个节点维护该区间对应的线性基。操作就是合并左右两个子节点的线性基 ( 操作)。查询时，将对应区间的若干个节点的线性基合并起来，然后在新基上查询最大值。复杂度较高，查询为。
只支持查询，无修改（离线）：对于静态区间的查询，可以使用 ST 表，预处理，查询。

6.3 带删除的线性基

解法：

使用离线算法：线段树分治，对于时间段建立线段树，并在其上 dfs，用栈维护其历史状态和更新信息。

将所有操作离线。每个数都有一个“生命周期”，即它被插入的时间和被删除的时间。
建立一棵以时间为轴的线段树。时间范围是，其中是总操作数。
对于一个生命周期为的数 x，我们将它“添加”到线段树上代表这个时间区间的若干个节点上。
从线段树的根节点开始进行深度优先搜索。
- 进入一个节点时，将该节点上存储的所有数插入到一个临时的线性基中。
- 如果当前节点是叶子节点，它代表一个具体的时间点。此时的线性基就是该时间点的答案，执行查询操作。
- 继续递归访问子节点。
- 退出一个节点时，需要撤销在该节点进行的操作，恢复线性基到进入该节点之前的状态。这通常通过一个栈来实现，记录每次插入修改了哪个以及它原来的值。

6.4 线性基与高斯消元的等价性

重申一遍这个重要的思想。一个的 01 矩阵（个数，每个数位），对其进行高斯消元，化为行阶梯形矩阵，得到的结果就是线性基。

矩阵的行空间（row space）就是所有行的线性组合构成的空间，这对应了数字集合的异或张成空间。
高斯消元的过程不改变行空间。
消元后的非零行构成行空间的一组基。这正对应了我们构造出的线性基。
矩阵的秩（非零行的数量）就是行空间的维数，也即线性基的大小。

理解这一点，有助于从更根本的层面把握线性基的原理，并可能启发将其思想应用到其他代数结构中。

7. 第六部分：不止异或线性基

我们在学习线性代数过程中提到的线性基通常是普通的向量加法和数乘，而不是异或。对于此类问题，我们的做法是：高斯消元。具体的问题要求可以搜索锣鼓题目P3265 [JLOI2015] 装备购买。

考虑一个向量是否与线性基线性相关，其实就是看是否存在一个解向量使得其在线性基矩阵变换下得到。而在高斯消元过程中，如果一行被消成了，那他就和已有的非零向量线性相关了。所以这个向量就不被纳入考虑。

8. 总结

线性基是一个将抽象的线性代数理论成功应用到具体算法问题中的典范。它看似神奇，但其背后是坚实而优美的数学原理。

核心思想：利用“基”的概念，为一组数（向量）的异或张成空间（向量空间）找到一个极小且性质优良的等价表示。
构造方法：模拟高斯消元，贪心地为每个“维度”（二进制位）寻找一个主元（基向量）。
核心应用：
- 最大/最小异或和：基于贪心思想。
- 第 k 小异或和：需要标准化的基和二进制编码思想。
- 可达性判断：模拟消元过程。
威力：将原本可能是指数级（个子集）的搜索空间，压缩到线性于位数（）的维度上进行高效计算。

Do not go gentle into that good night.