企业官网建设流程全解析

OI-wiki 线性基完全指南：从线性空间定义到异或线性基、求交与前缀线性基实战

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

线性基（Hamel 基）是线性空间理论的核心工具：一组数量尽可能少的线性无关向量，却能完整刻画整个空间的全部信息。在 OI / ICPC 竞赛中，线性基最常见的落地形态是异或线性基（$\mathbf{Z}_2^n$ 上的线性基），用于解决子集异或最大值 / 最小值 / 第 $k$ 大、异或方案计数、区间异或查询等经典问题。本文以 basis.md 为主线，结合 OI-wiki 仓库中 docs/math/code/basis/ 下的五份可直接运行的模板代码，从数学定义出发，逐步展开贪心法与高斯消元法两种构造、线性基的合并与求交（朴素算法与 Zassenhaus 算法）以及前缀线性基，读完即可上手洛谷 P3812、HDU 3949、CF 1100F 等经典题目。

从立体几何的基向量到线性基

回想高中数学立体几何中的基向量：在三维欧氏空间中取一组基向量 $\boldsymbol{i}$、$\boldsymbol{j}$、$\boldsymbol{k}$，空间中任意一个向量都可以由它们表示。换句话说，我们通过有限的基向量来描述无限的三维空间——这正是基向量的价值所在。

三维欧氏空间是特殊的 线性空间。所谓线性空间 $(V,+,\cdot,\Bbb{P})$，直观上就是一个满足八条公理（四条分配/结合律 + 单位元等）的代数结构：向量加法对应「叠加」，数乘对应「缩放」，域 $\Bbb{P}$ 中的元素对应「缩放比例」与「坐标取值范围」。把「基向量」推广到一般线性空间，就得到了线性基。

OI 中线性基的应用只涉及两类线性空间：

1. $n$ 维实线性空间$\mathbf{R}^n$——对应实数线性基；
2. $n$ 维布尔域线性空间$\mathbf{Z}_2^n$——对应异或线性基，其中加法是异或、数乘是与。

若读者不熟悉线性代数，建议先阅读 向量空间（线性空间） 一文再回到本指南。

线性基的定义与维数

定义：称线性空间 $V$ 的一个极大线性无关组为 $V$ 的一组Hamel 基或线性基，简称基。

• 规定线性空间 ${\theta}$（只含零向量的空间）的基为空集。
• 可以证明任意线性空间均存在线性基。由此定义线性空间 $V$ 的维数为线性基的元素个数（或势），记作 $\dim V$。

这一定义是后续一切性质与算法的基石：线性基本质上是"张成整个空间的最精简线性无关向量组"，其规模就是空间的维数。

线性基的基本性质

以下性质是解题时进行复杂度分析与正确性论证的依据。

有限维空间的四条核心性质

对于有限维线性空间 $V$，设其维数为 $n$，则：

1. $V$ 中的任意 $n+1$ 个向量线性相关；
2. $V$ 中的任意 $n$ 个线性无关的向量均为 $V$ 的基；
3. 若 $V$ 中的任意向量均可被向量组 $a_1,a_2,\dots,a_n$ 线性表出，则其是 $V$ 的一个基；
4. $V$ 中任意线性无关向量组 $a_1,a_2,\dots,a_m$ 均可通过插入一些向量使其变为 $V$ 的一个基。

???+ note "性质 3 的证明" 任取 $V$ 中的一组基 $b_1,b_2,\dots,b_n$，由已知条件，向量组 $b_1,b_2,\dots,b_n$ 可被 $a_1,a_2,\dots,a_n$ 线性表出，故

$$ n=\operatorname{rank}\{b_1,b_2,\dots,b_n\}\leq\operatorname{rank}\{a_1,a_2,\dots,a_n\}\leq n $$ 因此 $\operatorname{rank}\{a_1,a_2,\dots,a_n\}=n$，即 $a_1,\dots,a_n$ 本身就是一组基。

性质 4 说明：任何线性无关组都可以被"扩充"成基——这正是后续线性基求交、求极大线性无关组等算法的理论基础。

子空间维数公式

令 $V_1,V_2$ 是关于 $\Bbb{P}$ 的有限维线性空间，且 $V_1+V_2$ 和 $V_1\cap V_2$ 也是有限维的，则：

$$ \dim V_1+\dim V_2=\dim(V_1+V_2)+\dim(V_1\cap V_2) $$

???+ note "证明" 设 $\dim V_1=n_1$，$\dim V_2=n_2$，$\dim(V_1\cap V_2)=m$。取 $V_1\cap V_2$ 的一组基 $a_1,a_2,\dots,a_m$，将其分别扩充为 $V_1$ 和 $V_2$ 中的基： $a_1,\dots,a_m,b_1,\dots,b_{n_1-m}$ 与 $a_1,\dots,a_m,c_1,\dots,c_{n_2-m}$。

只需证明向量组 $a_1,\dots,a_m,b_1,\dots,b_{n_1-m},c_1,\dots,c_{n_2-m}$ 线性无关。设 $$ \sum_{i=1}^m r_ia_i+\sum_{i=1}^{n_1-m} s_ib_i+\sum_{i=1}^{n_2-m} t_ic_i=\theta $$ 则 $\sum_{i=1}^{n_2-m} t_ic_i=-\sum_{i=1}^m r_ia_i-\sum_{i=1}^{n_1-m} s_ib_i$。上式左边在 $V_2$ 中、右边在 $V_1$ 中，故两边均在 $V_1\cap V_2$ 中，因此 $\sum_{i=1}^{n_2-m} t_ic_i=\sum_{i=1}^m k_ia_i$，即 $c$ 组向量可由 $a$ 组基表出。由 $c$ 组与 $a$ 组合并线性无关可知 $t_1=\dots=t_{n_2-m}=k_1=\dots=k_m=0$，进而所有系数均为 $0$。故合并后的向量组线性无关，恰为 $V_1+V_2$ 的基，维数公式成立。

直和的等价条件

令 $V_1,V_2$ 是关于 $\Bbb{P}$ 的有限维线性空间，且 $V_1+V_2$ 和 $V_1\cap V_2$ 也是有限维的，则下列诸款等价：

1. $V_1+V_2=V_1\oplus V_2$（直和，即和空间中的元素分解唯一）；
2. $\dim V_1+\dim V_2=\dim(V_1+V_2)$；
3. 若 $a_1,\dots,a_n$ 是 $V_1$ 的一组基，$b_1,\dots,b_m$ 是 $V_2$ 的一组基，则 $a_1,\dots,a_n,b_1,\dots,b_m$ 是 $V_1+V_2$ 的一组基。

???+ note "Note" 第 1、3 两条可以推广到无限维线性空间。

直观例子：$\Bbb{R}^2$ 中的基

以二维平面 $\Bbb{R}^2$ 为例，可以直观感受"什么是基、什么不是"：

1. 如图basis-1.svg，不共线的两个向量 $u,v$ 是一组基——平面内任意向量都能由它们线性表出；
2. 换一对不共线的 $u,v$（basis-2.svg），仍然是一组基，这体现了基不唯一；
3. 如图basis-3.svg，$u=-v$，两者线性相关，不是一组基；
4. 如图basis-4.svg，$u,v,w$ 三个向量满足 $u+4v+6w=\theta$，线性相关，也不是一组基——$\Bbb{R}^2$ 的基必须恰有 2 个且线性无关。

正交基与单位正交基

若线性空间 $V$ 的一组基 $B$ 满足 $\forall b,b'\in B,\ (b,b')\ne 0\iff b=b'$（即两两正交），则称这组基是正交基。若还满足 $\forall b\in B,\ |b|=\sqrt{(b,b)}=1$，则称这组基是单位正交基。

任意有限维线性空间 $V$ 的基都可以通过 Schmidt 正交化（Gram–Schmidt 过程）变换为正交基。这一概念在实数线性基涉及内积（点积）计算、以及后续结合内积空间理论的题目中会用到。

应用总览

根据前文内容，线性基可以解决以下五类问题：

1. 求给定向量组的秩；
2. 对给定向量组，找到一组极大线性无关组（或其张成的线性空间的一组基）；
3. 向给定向量组插入某些向量后，在新向量组中找到一组极大线性无关组（或其张成的线性空间的一组基）；
4. 对找到的极大线性无关组（或基），判断某向量能否被其线性表出；
5. 对找到的极大线性无关组（或基），求其张成的线性空间中的特殊元素（如最大元、最小元等）。

在 OI 中，我们一般把 $n$ 维实线性空间 $\mathbf{R}^n$ 下的线性基称为实数线性基，把 $n$ 维布尔域线性空间 $\mathbf{Z}_2^n$ 下的线性基称为异或线性基。

???+ tip "Tip：$\mathbf{Z}_2^n$ 为什么是线性空间" $\mathbf{Z}_2$ 中的加法为异或、乘法为与，可以证明 $\mathbf{Z}_2$ 是域。进一步，代数系统 $(\mathbf{Z}_2^n,+,\cdot,\mathbf{Z}_2)$ 是线性空间，其中：

$$ (a_1,\dots,a_n)+(b_1,\dots,b_n):=(a_1+b_1,\dots,a_n+b_n), $$ $$ k\cdot(a_1,\dots,a_n):=(ka_1,\dots,ka_n). $$ 即**加法是异或、数乘是与**。这也是"异或线性基"名称的来源——子集异或和恰好对应 $n$ 维 0/1 向量在 $\mathbf{Z}_2$ 上的线性组合。

以异或线性基为例，给定一组布尔序列 $X={x_1,\dots,x_m}$，可构造一组异或线性基 $B={b_1,\dots,b_n}$，具有三条关键性质：

1. $B$ 中任意非空子集的异或和不为 $0$（即 $B$ 线性无关）；
2. 对 $X$ 中的任意元素 $x$，都可在 $B$ 中取出若干元素使其异或和为 $x$（即 $B$ 能张成 $X$）；
3. 对任意满足上述两条的集合 $B'$，其元素个数不会小于 $B$ 的元素个数（即 $B$ 是最精简的）。

由此，异或线性基可直接实现：

1. 判断一个数能否表示成某数集子集的异或和；
2. 求一个数表示成某数集子集异或和的方案数；
3. 求某数集子集异或和的最大值 / 最小值 / 第 $k$ 大 / 第 $k$ 小；
4. 求一个数在某数集子集异或和中的排名。

异或线性基的构造方法

因为异或线性基与实数线性基没有本质差别，接下来以异或线性基为例展开；实数线性基版本的代码只需做一点简单修改即可。

贪心法

插入：对原集合的每个数 $p$ 转为二进制，从高位向低位扫。对于第 $x$ 位是 $1$ 的位：

• 若 $a_x$ 不存在，令 $a_x \leftarrow p$ 并结束扫描；
• 若 $a_x$ 存在，令 $p \leftarrow p~\text{xor}~a_x$ 继续扫描。

查询最大值：将线性基从高位向低位扫，若异或上当前扫到的 $a_x$ 使答案变大，就把答案异或上 $a_x$。原理：从高往低位扫时，若当前扫到第 $i$ 位，意味着可以保证答案的第 $i$ 位为 $1$，且后面没有机会再改变第 $i$ 位。

查询最小值：直接取线性基集合所有元素中最小的那个。

判断某个数能否被异或出来：类似于插入过程，如果最后插入的数 $p$ 被异或成了 $0$，则能被异或出来。

仓库中的完整模板 basis_1.cpp（对应洛谷 P3812【模板】线性基）：

#include <algorithm> #include <iostream> using ull = unsigned long long; ull p[64]; void insert(ull x) { for (int i = 63; ~i; --i) { if (!(x >> i)) // x 的第 i 位是 0 continue; if (!p[i]) { p[i] = x; break; } x ^= p[i]; } } using std::cin; using std::cout; int main() { int n; cin >> n; ull a; for (int i = 1; i <= n; ++i) { cin >> a; insert(a); } ull ans = 0; for (int i = 63; ~i; --i) { ans = std::max(ans, ans ^ p[i]); } cout << ans << '\n'; return 0; }

代码要点：p[i]表示最高位为第 $i$ 位的基向量（用unsigned long long存储，覆盖 64 位）；插入时从63到0高位贪心；最终求最大值同样从高位贪心取max(ans, ans ^ p[i])。

高斯消元法

高斯消元法相当于从线性方程组的视角构造线性基：把每个数看成一行，做行变换化简成行阶梯形（行最简形），保留的主元行即为线性基。正确性显然——行变换不改变行向量组张成的空间。

仓库中的完整模板 basis_2.cpp：

#include <iostream> using ull = unsigned long long; constexpr int MAXN = 1e5 + 5; ull deg(ull num, int deg) { return num & (1ull << deg); } ull a[MAXN]; using std::cin; using std::cout; int main() { cin.tie(nullptr)->sync_with_stdio(false); int n; cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; int row = 1; for (int col = 63; ~col && row <= n; --col) { for (int i = row; i <= n; ++i) { if (deg(a[i], col)) { std::swap(a[row], a[i]); break; } } if (!deg(a[row], col)) continue; for (int i = 1; i <= n; ++i) { if (i == row) continue; if (deg(a[i], col)) { a[i] ^= a[row]; } } ++row; } ull ans = 0; for (int i = 1; i < row; ++i) { ans ^= a[i]; } cout << ans << '\n'; return 0; }

两种构造的性质对比

贪心法构造的线性基具有如下性质：

• 线性基中没有异或和为 $0$ 的子集；
• 线性基中各数二进制最高位不同。

高斯消元法构造出的线性基满足更强的一条性质：

• 高斯消元后的矩阵是一个行简化阶梯形矩阵。

该性质包含了贪心法构造的线性基满足的两条性质。

不理解这条性质时，可以跳转 高斯消元 一文了解行阶梯形与行最简形的定义。

样例验证（文档提供的测试数据）：

5 633 211 169 841 1008

二进制表示：

1001111001 0011010011 0010101001 1101001001 1111110000

贪心法生成的线性基：

1001111001 0100110000 0011010011 0001111010 0000000000 0000010000 0000000000 0000000000 0000000000 0000000000

高斯消元法生成的线性基（行简化阶梯形）：

1000000011 0100100000 0010101001 0001101010 0000010000 0000000000 0000000000 0000000000 0000000000 0000000000

行最简形性质非常有用。例如求最大异或和：贪心法构造的线性基还需要再扫一遍贪心（若ans当前位是0，异或一定更优；当前位为1则一定不会更优）；而高斯消元法构造后直接将线性基中所有元素异或起来输出即可——行最简形保证了每一行贡献互不干扰，见 basis_2.cpp 中ans ^= a[i]的写法。

对于查询一个数能否被异或得到、查询第 $k$ 大异或和等经典问题，高斯消元法得到的线性基同样更方便：可以直接"按二进制位自由组合"，配合排位思想求解第 $k$ 大。

时间复杂度

设向量长度为 $n$、总数为 $m$：

• 贪心法：$O(nm)$，每次插入至多扫 $n$ 位；
• 高斯消元法：$O(nm)$，其中常数略大（每确定一个主元列要对其余所有行做一次消元）；
• 实数线性基：$O(n^2m)$（处理实数运算时需要更复杂的消元步骤）。

线性基的合并与求交

线性基合并

线性基的合并只需暴力处理：将要合并的一组线性基中的向量逐一插入另一组线性基即可。单次合并的时间复杂度为 $O(n^2)$（异或线性基）或 $O(n^3)$（实数线性基），其中 $n$ 为向量长度。

线性基求交

线性基求交，严格地说，是求两个线性基张成的线性空间的交空间的一组线性基。本节介绍两种算法，单次求交的时间复杂度都是 $O(n^2)$（异或线性基）或 $O(n^3)$（实数线性基）。两者的对应问题为 Library Checker 上的 Intersection of $\mathbf F_2$ vector spaces 模板题。

朴素算法

设要求交的线性基分别为 $\alpha$ 和 $\beta$。朴素算法只需对"暴力合并"做如下调整（以异或线性基为例）：

• 将 $\beta$ 中的向量 $\beta_j$ 利用贪心法尝试插入 $\alpha$，并初始化交 $\gamma$ 为空集；
• 插入时记录 $\beta$ 中元素的贡献：维持一个新向量 $b$，初始化为 $\beta_j$；若正在插入的向量与线性基第 $x$ 位的向量取了异或，则贡献 $b$ 也要与第 $x$ 位记录的贡献 $b_x$ 异或一次；
• 若插入成功（在第 $x$ 位插入了向量 $\beta_j'$），将第 $x$ 位记录的 $b_x$ 更新为得到 $\beta_j'$ 过程中 $\beta$ 中元素的贡献 $b$；
• 若插入不成功，将过程中记录的贡献 $b$ 插入到 $\gamma$ 中。

最终得到的 $\gamma$ 就是所求的交；该算法同时求出了线性基的并。

???+ note "对算法的解释" 设合并后的线性基为 ${\alpha_1,\cdots,\alpha_m,\beta'{j_1},\cdots,\beta'{j_\ell}}$，其中 $\beta'{j_k}$ 是插入 $\beta{j_k}$ 时最后得到的向量，则 ${\alpha_1,\cdots,\alpha_m,\beta_{j_1},\cdots,\beta_{j_\ell}}$ 同样是一组合并后的线性基。记 $\beta^+$ 为集合 ${\beta_{j_1},\cdots,\beta_{j_\ell}}$，则和空间中的每个向量 $c$ 都可唯一地表示成

$$ c = a\oplus b $$ 的形式，其中 $a\in\operatorname{span}\alpha$、$b\in\operatorname{span}\beta^+$。算法中记录的「贡献 $b$」就是在维护这个分解的 $b$ 项：对于成功插入，最后记录的 $b$ 恰为该分解中的 $b$；对于不成功插入，最终 $0=a\oplus b$，此时 $b=a$ 必位于交空间 $\operatorname{span}\alpha\cap\operatorname{span}\beta$ 中。可以进一步证明，所有不成功插入所记录的 $b$ 恰好共同张成交空间——因此将它们全部插入 $\gamma$ 即得交的线性基。若改为维护 $\alpha$ 中元素的贡献（每个 $\alpha_i$ 初始贡献为 $\alpha_i$，插入的 $\beta_j$ 初始贡献为 $0$），得到的结果同样正确。

仓库模板 basis_intersect_1.cpp 完整实现了该算法：intersect方法中数组c是 $\alpha$ 的拷贝，b_parts记录每一位的贡献，扫描rhs（即 $\beta$）的每个向量后，把无法插入时得到的b_part插入结果集res。

class LinearBasis { static constexpr int K = 30; std::array<int, K> a; ... // Return a basis for *THIS intersecting RHS. LinearBasis intersect(const LinearBasis& rhs) const { LinearBasis res; std::array<int, K> c = a, b_parts = {}; for (int i = K - 1; ~i; --i) { int x = rhs.a[i], b_part = x; for (int k = i; ~k && x; --k) { if ((x >> k) & 1) { if (!c[k]) { c[k] = x; b_parts[k] = b_part; } x ^= c[k]; b_part ^= b_parts[k]; } } res.insert(b_part); } return res; } };

Zassenhaus 算法

另一种等价做法是Zassenhaus 算法，它同样可以同时求出两个线性基的并和交，复杂度与朴素算法完全一致。具体步骤如下：

• 初始化一个向量长度为 $2n$ 的线性基 $\gamma$ 为空，其中每个向量写成 $(a,b)$ 的形式，$a$ 和 $b$ 长度均为 $n$；
• 将 $\alpha$ 中的元素 $\alpha_i$ 以 $(\alpha_i,\alpha_i)$ 的形式插入 $\gamma$；
• 将 $\beta$ 中的元素 $\beta_j$ 以 $(\beta_j,0)$ 的形式插入 $\gamma$；
• 最后得到的 $\gamma$ 中所有非零元素 $(c_k,d_k)$：$c_k$ 非零的那些向量中 $c_k$ 的全体组成 $\alpha$ 与 $\beta$ 的并的线性基；$c_k$ 为零的那些向量中 $d_k$ 的全体组成交的线性基。

算法中构造线性基的方法可以是贪心法或高斯消元法，只要保证 $\gamma$ 中的线性基组成行阶梯型矩阵即可。将 Zassenhaus 算法的消元步骤与朴素算法对比可发现：基于贪心法的 Zassenhaus 算法相当于"维护 $\alpha$ 中元素的贡献"的朴素算法；若先插入所有 $(\alpha_i,0)$ 再插入所有 $(\beta_j,\beta_j)$，则等价于"维护 $\beta$ 中元素贡献"的朴素算法。

???+ note "正确性证明（一般化）" 设 $V$ 为一线性空间，子空间 $U=\operatorname{span}\alpha$、$W=\operatorname{span}\beta$。算法相当于通过化简行阶梯型来求子空间

$$ H = \operatorname{span}(\{(\alpha_i,\alpha_i)\}\cup\{(\beta_j,0)\}) $$ 的一组基 $\gamma$。考察投影映射 $\pi:H\rightarrow V,\ (a,b)\mapsto a$，则 $\pi(H)=U+W$，且 $$ \ker\pi = H\cap(\{0\}\times V) = \{0\}\times(U\cap W). $$ 由线性映射的核空间与像空间定理（见 [线性映射](https://link.gitcode.com/i/15379f4d5b54ca7b8795d10d16c64493) 一文）有 $\dim H=\dim(U+W)+\dim(U\cap W)$。行阶梯型的前几列仍是行阶梯型，故 $c_k\ne 0$ 的行数恰好等于 $\dim(U+W)$ 且这些 $c_k$ 形成 $U+W$ 的一组基；剩余非零行恰有 $\dim(U\cap W)$ 个且 $c_k=0$，对应的 $d_k$ 均落在 $U\cap W$ 中且线性无关，因而构成交空间的一组基。

仓库模板 basis_intersect_2.cpp 用巧妙的位运算实现了上述过程：用一个long long的高 $K$ 位存储 $a$、低 $K$ 位存储 $b$，插入 $\alpha$ 时写入((long long)x << K) | x（即 $(\alpha_i,\alpha_i)$），插入 $\beta$ 时写入(long long)x << K（即 $(\beta_j,0)$）。输出时只需考虑前 $n$ 位均为零的向量，即c.print(K)只统计低 $K$ 位。

int main() { constexpr int K = 30; int t; std::cin >> t; for (; t; --t) { LinearBasis c(K << 1); int n; std::cin >> n; for (; n; --n) { int x; std::cin >> x; c.insert(((long long)x << K) | x); // 以 (α_i, α_i) 形式插入 } int m; std::cin >> m; for (; m; --m) { int x; std::cin >> x; c.insert((long long)x << K); // 以 (β_j, 0) 形式插入 } c.print(K); // 输出交空间基（前 n 位为零的 d_k） } return 0; }

拓展：前缀线性基（时间戳线性基）

本节只讨论异或线性基的情形，并假设单个向量可存储在 $O(1)$ 空间内、单次操作复杂度为 $O(1)$。

动机：需要多次查询区间异或最大值时，一种常见做法是 猫树 配合线性基，时间复杂度为 $O(nm\log m+n^2q)$（$n$ 为向量长度，$m$ 为序列长度，$q$ 为询问次数）。另一种做法是利用前缀线性基（或称时间戳线性基），将复杂度降到 $O(n(m+q))$。

核心思想：对序列的每个前缀都维护该前缀所有后缀的线性基，从而支持查询任意区间的线性基。注意到前缀 $[1,i]$ 的所有后缀 $[j,i]$ 的线性基相互包含（$[j,i]$ 的线性基总包含 $[j+1,i]$ 的线性基），因此互不相同的至多只有 $n$ 种，且可由空集逐步添加新向量得到。利用该单调性，只需为每个保留的向量 $v$ 标记它出现的最大下标 $t$，即可在 $O(n)$ 空间内存储所有后缀的线性基。查询区间 $[j,i]$ 时，在 $i$ 处的前缀线性基中仅保留标记 $t\ge j$ 的向量即可。

形式化地说，向量 $v$ 的时间戳为

$$ t(v) = \max{j:\exists i_1,\cdots,i_k\in[j,i]\ \text{s.t.}\ v=v_{i_1}\oplus v_{i_2}\oplus\cdots\oplus v_{i_k}}. $$

即 $v$ 所能被表示的方案中，最小下标的最大值。这启发我们：维护时间戳时，贪心地用"尽可能新的向量"替换"旧的向量"即可。

基于贪心法构造的前缀线性基，在插入时做了如下调整：

• 为线性基中保留的每个向量 $a_x$ 保存时间戳 $t_x$，初始均为 $0$；
• 要添加序列中第 $i$ 个向量 $v$ 时，仍从高位向低位扫，同时记录当前时间 $i$；
• 若 $v$ 的第 $x$ 位是 $1$，比较已有向量 $a_x$ 的时间戳 $t_x$ 与当前时间 $i$：
  • 若 $i>t_x$（新向量时间更晚）：将 $a_x$ 设为 $v$，时间戳更新为 $i$，并把旧的 $a_x\oplus v$ 按旧时间戳 $t_x$ 继续添加；
  • 若 $i<t_x$（新向量时间更早）：保留 $a_x$ 与 $t_x$，将 $v$ 异或 $a_x$ 后继续。

即：当前位能用较新向量表示就用较新的，否则保留原向量。注意更新位置 $x$ 时不能把异或结果 $a_x\oplus v$ 存回位置 $x$，因为 $a_x\oplus v$ 的时间戳为 $\min{t(a_x),t(v)}=t(a_x)$，小于 $v$ 的时间戳。同样的原因，高斯消元法在向上更新时可能破坏时间戳性质，因此不适用于构造前缀线性基。

仓库模板 prefix_basis.cpp（对应 Codeforces 1100F Ivan and Burgers）完整实现了插入与查询：

class LinearBasis { static constexpr int K = 20; std::array<int, K> a, t; public: LinearBasis() : a{}, t{} {} // Insert vector x at time i. void insert(int x, int i) { for (int k = K - 1; ~k && x; --k) { if (((x >> k) & 1)) { if (i > t[k]) { std::swap(a[k], x); // 新向量更晚，替换并携带旧向量继续 std::swap(t[k], i); } x ^= a[k]; } } } // Find max xor of subsets of elements from time i till now. int query(int i) const { int res = 0; for (int k = K - 1; ~k; --k) { if (t[k] >= i && (res ^ a[k]) > res) { res ^= a[k]; } } return res; } };

主程序按右端点排序离线处理询问：依次插入序列元素lb.insert(c[i], i)，当右端点到达qu[ids[j]][1]时调用lb.query(qu[ids[j]][0])回答左端点在该处的区间最大值询问。仓库示例数据见 docs/math/examples/basis/prefix_basis.in（5 个元素12 14 23 13 7与 15 个区间询问）。

如果需要在线询问，也可以用 $O(mn)$ 的空间把每个前缀处的前缀线性基都存下来再查询——这可以看作一种「可持久化」线性基；若需要用到高斯消元法得到的线性基（行最简形）的性质，可以在查询时另行处理。

复杂度速查表

练习与延伸阅读

经典练习题（均为线性基领域的标志性题目，可与上述模板一一对应）：

• Luogu P3812【模板】线性基——两种构造模板的直接应用；
• AcWing 3164. 线性基——模板级练习；
• SGU 275 to xor or not xor——最大异或和；
• HDU 3949 XOR——第 $k$ 大异或和（配合高斯消元行最简形）；
• HDU 6579 Operation——在线查询 + 可持久化变体；
• Luogu P4151 [WC2011] 最大 XOR 和路径——图上问题与线性基结合；
• Library Checker - Intersection of F2 vector spaces——线性基求交模板题；
• AtCoder AGC045 A - Xor Battle——博弈与线性基结合；
• Codeforces 1100F Ivan and Burgers——前缀线性基（区间最大异或和）；
• Luogu P3292 [SCOI2016] 幸运数字——树链 + 线性基综合应用。

仓库内继续深入阅读：

• 线性基的数学基础：向量空间（线性相关、极大线性无关组、秩、子空间、直和）；
• 求交正确性证明依赖的核空间与像空间定理：线性映射；
• 高斯消元法的行最简形背景：高斯消元；
• 前缀线性基的替代方案：猫树；
• 全部可运行模板代码位于 docs/math/code/basis/，对应示例数据位于 docs/math/examples/basis/。

参考资料

1. 丘维声，《高等代数（下）》，清华大学出版社。
2. Basis (linear algebra)，Wikipedia。
3. Vector Basis，Wolfram MathWorld。
4. Zassenhaus algorithm，Wikipedia。

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki