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 中线性基的应用只涉及两类线性空间$n$ 维实线性空间$\mathbf{R}^n$——对应实数线性基$n$ 维布尔域线性空间$\mathbf{Z}_2^n$——对应异或线性基其中加法是异或、数乘是与。若读者不熟悉线性代数建议先阅读 向量空间线性空间 一文再回到本指南。线性基的定义与维数定义称线性空间 $V$ 的一个极大线性无关组为 $V$ 的一组Hamel 基或线性基简称基。规定线性空间 ${\theta}$只含零向量的空间的基为空集。可以证明任意线性空间均存在线性基。由此定义线性空间 $V$ 的维数为线性基的元素个数或势记作 $\dim V$。这一定义是后续一切性质与算法的基石线性基本质上是张成整个空间的最精简线性无关向量组其规模就是空间的维数。线性基的基本性质以下性质是解题时进行复杂度分析与正确性论证的依据。有限维空间的四条核心性质对于有限维线性空间 $V$设其维数为 $n$则$V$ 中的任意 $n1$ 个向量线性相关$V$ 中的任意 $n$ 个线性无关的向量均为 $V$ 的基若 $V$ 中的任意向量均可被向量组 $a_1,a_2,\dots,a_n$ 线性表出则其是 $V$ 的一个基$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_1V_2$ 和 $V_1\cap V_2$ 也是有限维的则$$ \dim V_1\dim V_2\dim(V_1V_2)\dim(V_1\cap V_2) $$??? note 证明 设 $\dim V_1n_1$$\dim V_2n_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_{i1}^m r_ia_i\sum_{i1}^{n_1-m} s_ib_i\sum_{i1}^{n_2-m} t_ic_i\theta $$ 则 $\sum_{i1}^{n_2-m} t_ic_i-\sum_{i1}^m r_ia_i-\sum_{i1}^{n_1-m} s_ib_i$。上式左边在 $V_2$ 中、右边在 $V_1$ 中故两边均在 $V_1\cap V_2$ 中因此 $\sum_{i1}^{n_2-m} t_ic_i\sum_{i1}^m k_ia_i$即 $c$ 组向量可由 $a$ 组基表出。由 $c$ 组与 $a$ 组合并线性无关可知 $t_1\dotst_{n_2-m}k_1\dotsk_m0$进而所有系数均为 $0$。故合并后的向量组线性无关恰为 $V_1V_2$ 的基维数公式成立。直和的等价条件令 $V_1,V_2$ 是关于 $\Bbb{P}$ 的有限维线性空间且 $V_1V_2$ 和 $V_1\cap V_2$ 也是有限维的则下列诸款等价$V_1V_2V_1\oplus V_2$直和即和空间中的元素分解唯一$\dim V_1\dim V_2\dim(V_1V_2)$若 $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_1V_2$ 的一组基。??? note Note 第 1、3 两条可以推广到无限维线性空间。直观例子$\Bbb{R}^2$ 中的基以二维平面 $\Bbb{R}^2$ 为例可以直观感受什么是基、什么不是如图basis-1.svg不共线的两个向量 $u,v$ 是一组基——平面内任意向量都能由它们线性表出换一对不共线的 $u,v$basis-2.svg仍然是一组基这体现了基不唯一如图basis-3.svg$u-v$两者线性相关不是一组基如图basis-4.svg$u,v,w$ 三个向量满足 $u4v6w\theta$线性相关也不是一组基——$\Bbb{R}^2$ 的基必须恰有 2 个且线性无关。正交基与单位正交基若线性空间 $V$ 的一组基 $B$ 满足 $\forall b,b\in B,\ (b,b)\ne 0\iff bb$即两两正交则称这组基是正交基。若还满足 $\forall b\in B,\ |b|\sqrt{(b,b)}1$则称这组基是单位正交基。任意有限维线性空间 $V$ 的基都可以通过 Schmidt 正交化Gram–Schmidt 过程变换为正交基。这一概念在实数线性基涉及内积点积计算、以及后续结合内积空间理论的题目中会用到。应用总览根据前文内容线性基可以解决以下五类问题求给定向量组的秩对给定向量组找到一组极大线性无关组或其张成的线性空间的一组基向给定向量组插入某些向量后在新向量组中找到一组极大线性无关组或其张成的线性空间的一组基对找到的极大线性无关组或基判断某向量能否被其线性表出对找到的极大线性无关组或基求其张成的线性空间中的特殊元素如最大元、最小元等。在 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_1b_1,\dots,a_nb_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}$具有三条关键性质$B$ 中任意非空子集的异或和不为 $0$即 $B$ 线性无关对 $X$ 中的任意元素 $x$都可在 $B$ 中取出若干元素使其异或和为 $x$即 $B$ 能张成 $X$对任意满足上述两条的集合 $B$其元素个数不会小于 $B$ 的元素个数即 $B$ 是最精简的。由此异或线性基可直接实现判断一个数能否表示成某数集子集的异或和求一个数表示成某数集子集异或和的方案数求某数集子集异或和的最大值 / 最小值 / 第 $k$ 大 / 第 $k$ 小求一个数在某数集子集异或和中的排名。异或线性基的构造方法因为异或线性基与实数线性基没有本质差别接下来以异或线性基为例展开实数线性基版本的代码只需做一点简单修改即可。贪心法插入对原集合的每个数 $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$对于不成功插入最终 $0a\oplus b$此时 $ba$ 必位于交空间 $\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::arrayint, K a; ... // Return a basis for *THIS intersecting RHS. LinearBasis intersect(const LinearBasis rhs) const { LinearBasis res; std::arrayint, 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)UW$且 $$ \ker\pi H\cap(\{0\}\times V) \{0\}\times(U\cap W). $$ 由线性映射的核空间与像空间定理见 [线性映射](https://link.gitcode.com/i/15379f4d5b54ca7b8795d10d16c64493) 一文有 $\dim H\dim(UW)\dim(U\cap W)$。行阶梯型的前几列仍是行阶梯型故 $c_k\ne 0$ 的行数恰好等于 $\dim(UW)$ 且这些 $c_k$ 形成 $UW$ 的一组基剩余非零行恰有 $\dim(U\cap W)$ 个且 $c_k0$对应的 $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 mn^2q)$$n$ 为向量长度$m$ 为序列长度$q$ 为询问次数。另一种做法是利用前缀线性基或称时间戳线性基将复杂度降到 $O(n(mq))$。核心思想对序列的每个前缀都维护该前缀所有后缀的线性基从而支持查询任意区间的线性基。注意到前缀 $[1,i]$ 的所有后缀 $[j,i]$ 的线性基相互包含$[j,i]$ 的线性基总包含 $[j1,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.}\ vv_{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$若 $it_x$新向量时间更晚将 $a_x$ 设为 $v$时间戳更新为 $i$并把旧的 $a_x\oplus v$ 按旧时间戳 $t_x$ 继续添加若 $it_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::arrayint, 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.in5 个元素12 14 23 13 7与 15 个区间询问。如果需要在线询问也可以用 $O(mn)$ 的空间把每个前缀处的前缀线性基都存下来再查询——这可以看作一种「可持久化」线性基若需要用到高斯消元法得到的线性基行最简形的性质可以在查询时另行处理。复杂度速查表操作异或线性基实数线性基贪心构造$n$ 维、$m$ 个向量$O(nm)$$O(n^2m)$高斯消元构造$O(nm)$常数略大$O(n^2m)$线性基合并单次$O(n^2)$$O(n^3)$线性基求交朴素 / Zassenhaus单次$O(n^2)$$O(n^3)$前缀线性基离线区间查询$q$ 次询问$O(n(mq))$—练习与延伸阅读经典练习题均为线性基领域的标志性题目可与上述模板一一对应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/。参考资料丘维声《高等代数下》清华大学出版社。Basis (linear algebra)Wikipedia。Vector BasisWolfram MathWorld。Zassenhaus algorithmWikipedia。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 OI-wiki 线性基完全指南：从线性空间定义到异或线性基、求交与前缀线性基实战
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 中线性基的应用只涉及两类线性空间$n$ 维实线性空间$\mathbf{R}^n$——对应实数线性基$n$ 维布尔域线性空间$\mathbf{Z}_2^n$——对应异或线性基其中加法是异或、数乘是与。若读者不熟悉线性代数建议先阅读 向量空间线性空间 一文再回到本指南。线性基的定义与维数定义称线性空间 $V$ 的一个极大线性无关组为 $V$ 的一组Hamel 基或线性基简称基。规定线性空间 ${\theta}$只含零向量的空间的基为空集。可以证明任意线性空间均存在线性基。由此定义线性空间 $V$ 的维数为线性基的元素个数或势记作 $\dim V$。这一定义是后续一切性质与算法的基石线性基本质上是张成整个空间的最精简线性无关向量组其规模就是空间的维数。线性基的基本性质以下性质是解题时进行复杂度分析与正确性论证的依据。有限维空间的四条核心性质对于有限维线性空间 $V$设其维数为 $n$则$V$ 中的任意 $n1$ 个向量线性相关$V$ 中的任意 $n$ 个线性无关的向量均为 $V$ 的基若 $V$ 中的任意向量均可被向量组 $a_1,a_2,\dots,a_n$ 线性表出则其是 $V$ 的一个基$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_1V_2$ 和 $V_1\cap V_2$ 也是有限维的则$$ \dim V_1\dim V_2\dim(V_1V_2)\dim(V_1\cap V_2) $$??? note 证明 设 $\dim V_1n_1$$\dim V_2n_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_{i1}^m r_ia_i\sum_{i1}^{n_1-m} s_ib_i\sum_{i1}^{n_2-m} t_ic_i\theta $$ 则 $\sum_{i1}^{n_2-m} t_ic_i-\sum_{i1}^m r_ia_i-\sum_{i1}^{n_1-m} s_ib_i$。上式左边在 $V_2$ 中、右边在 $V_1$ 中故两边均在 $V_1\cap V_2$ 中因此 $\sum_{i1}^{n_2-m} t_ic_i\sum_{i1}^m k_ia_i$即 $c$ 组向量可由 $a$ 组基表出。由 $c$ 组与 $a$ 组合并线性无关可知 $t_1\dotst_{n_2-m}k_1\dotsk_m0$进而所有系数均为 $0$。故合并后的向量组线性无关恰为 $V_1V_2$ 的基维数公式成立。直和的等价条件令 $V_1,V_2$ 是关于 $\Bbb{P}$ 的有限维线性空间且 $V_1V_2$ 和 $V_1\cap V_2$ 也是有限维的则下列诸款等价$V_1V_2V_1\oplus V_2$直和即和空间中的元素分解唯一$\dim V_1\dim V_2\dim(V_1V_2)$若 $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_1V_2$ 的一组基。??? note Note 第 1、3 两条可以推广到无限维线性空间。直观例子$\Bbb{R}^2$ 中的基以二维平面 $\Bbb{R}^2$ 为例可以直观感受什么是基、什么不是如图basis-1.svg不共线的两个向量 $u,v$ 是一组基——平面内任意向量都能由它们线性表出换一对不共线的 $u,v$basis-2.svg仍然是一组基这体现了基不唯一如图basis-3.svg$u-v$两者线性相关不是一组基如图basis-4.svg$u,v,w$ 三个向量满足 $u4v6w\theta$线性相关也不是一组基——$\Bbb{R}^2$ 的基必须恰有 2 个且线性无关。正交基与单位正交基若线性空间 $V$ 的一组基 $B$ 满足 $\forall b,b\in B,\ (b,b)\ne 0\iff bb$即两两正交则称这组基是正交基。若还满足 $\forall b\in B,\ |b|\sqrt{(b,b)}1$则称这组基是单位正交基。任意有限维线性空间 $V$ 的基都可以通过 Schmidt 正交化Gram–Schmidt 过程变换为正交基。这一概念在实数线性基涉及内积点积计算、以及后续结合内积空间理论的题目中会用到。应用总览根据前文内容线性基可以解决以下五类问题求给定向量组的秩对给定向量组找到一组极大线性无关组或其张成的线性空间的一组基向给定向量组插入某些向量后在新向量组中找到一组极大线性无关组或其张成的线性空间的一组基对找到的极大线性无关组或基判断某向量能否被其线性表出对找到的极大线性无关组或基求其张成的线性空间中的特殊元素如最大元、最小元等。在 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_1b_1,\dots,a_nb_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}$具有三条关键性质$B$ 中任意非空子集的异或和不为 $0$即 $B$ 线性无关对 $X$ 中的任意元素 $x$都可在 $B$ 中取出若干元素使其异或和为 $x$即 $B$ 能张成 $X$对任意满足上述两条的集合 $B$其元素个数不会小于 $B$ 的元素个数即 $B$ 是最精简的。由此异或线性基可直接实现判断一个数能否表示成某数集子集的异或和求一个数表示成某数集子集异或和的方案数求某数集子集异或和的最大值 / 最小值 / 第 $k$ 大 / 第 $k$ 小求一个数在某数集子集异或和中的排名。异或线性基的构造方法因为异或线性基与实数线性基没有本质差别接下来以异或线性基为例展开实数线性基版本的代码只需做一点简单修改即可。贪心法插入对原集合的每个数 $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$对于不成功插入最终 $0a\oplus b$此时 $ba$ 必位于交空间 $\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::arrayint, K a; ... // Return a basis for *THIS intersecting RHS. LinearBasis intersect(const LinearBasis rhs) const { LinearBasis res; std::arrayint, 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)UW$且 $$ \ker\pi H\cap(\{0\}\times V) \{0\}\times(U\cap W). $$ 由线性映射的核空间与像空间定理见 [线性映射](https://link.gitcode.com/i/15379f4d5b54ca7b8795d10d16c64493) 一文有 $\dim H\dim(UW)\dim(U\cap W)$。行阶梯型的前几列仍是行阶梯型故 $c_k\ne 0$ 的行数恰好等于 $\dim(UW)$ 且这些 $c_k$ 形成 $UW$ 的一组基剩余非零行恰有 $\dim(U\cap W)$ 个且 $c_k0$对应的 $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 mn^2q)$$n$ 为向量长度$m$ 为序列长度$q$ 为询问次数。另一种做法是利用前缀线性基或称时间戳线性基将复杂度降到 $O(n(mq))$。核心思想对序列的每个前缀都维护该前缀所有后缀的线性基从而支持查询任意区间的线性基。注意到前缀 $[1,i]$ 的所有后缀 $[j,i]$ 的线性基相互包含$[j,i]$ 的线性基总包含 $[j1,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.}\ vv_{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$若 $it_x$新向量时间更晚将 $a_x$ 设为 $v$时间戳更新为 $i$并把旧的 $a_x\oplus v$ 按旧时间戳 $t_x$ 继续添加若 $it_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::arrayint, 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.in5 个元素12 14 23 13 7与 15 个区间询问。如果需要在线询问也可以用 $O(mn)$ 的空间把每个前缀处的前缀线性基都存下来再查询——这可以看作一种「可持久化」线性基若需要用到高斯消元法得到的线性基行最简形的性质可以在查询时另行处理。复杂度速查表操作异或线性基实数线性基贪心构造$n$ 维、$m$ 个向量$O(nm)$$O(n^2m)$高斯消元构造$O(nm)$常数略大$O(n^2m)$线性基合并单次$O(n^2)$$O(n^3)$线性基求交朴素 / Zassenhaus单次$O(n^2)$$O(n^3)$前缀线性基离线区间查询$q$ 次询问$O(n(mq))$—练习与延伸阅读经典练习题均为线性基领域的标志性题目可与上述模板一一对应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/。参考资料丘维声《高等代数下》清华大学出版社。Basis (linear algebra)Wikipedia。Vector BasisWolfram MathWorld。Zassenhaus algorithmWikipedia。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考