1. 从一道经典面试题说起异或运算的魔力如果你刷过一些算法题或者对数据结构和竞赛算法有所涉猎大概率见过这样一类问题给定一个非负整数集合如何从中选出若干个数进行异或XOR运算使得结果最大或者这个集合能通过异或运算产生多少个不同的非负整数又或者能否从集合中选出一个子集使其异或和等于某个给定的目标值我第一次遇到这类问题是在准备面试时题目大意是给你一个数组nums找出一个最大的子序列异或和。当时我的第一反应是暴力枚举所有子集复杂度是指数级的显然不可行。后来了解到可以用一种叫做“线性基”的数据结构来高效解决其核心思想是将一组数表示成二进制向量然后通过类似高斯消元的方法得到一组“基”。这听起来有点抽象但它的威力在于能将一个可能很大的集合压缩成至多几十个数对于64位整数最多64个并且这几十个数保留了原集合所有可能的异或结果信息。从此这类“异或最大值”、“异或第k小值”等问题就从看似无解的搜索变成了O(n * log(max_val))的预处理加上O(log max_val)的单次查询。线性基本质上是一种处理异或空间的利器。它处理的不是我们熟悉的实数向量空间而是定义在模2域GF(2)上的向量空间向量的每个分量就是二进制位向量的加法就是异或运算。理解了这一点很多操作就变得顺理成章。这篇文章我就结合自己刷题和实际编码中的理解拆解一下线性基的原理、构建、基本操作以及一些不那么“模板”的实战技巧和坑点。无论你是为了应对算法面试还是想在竞赛中多掌握一件趁手兵器相信这篇详尽的梳理都能帮到你。2. 线性基的核心原理异或空间里的“基底”要理解线性基我们必须先跳出十进制数字的视角进入二进制的世界。对于一个非负整数比如13二进制1101我们可以把它看作一个四维的向量(1, 1, 0, 1)这里的维度对应着从低到高的每一个二进制位。在这个视角下两个数的异或运算就对应着它们向量表示的按位模2加法。模2加法的规则很简单000 011 101 110进位舍弃。这正是异或的规则。那么给定一个整数集合S所有由S中元素通过任意次异或运算能得到的结果就构成了一个“向量空间”更准确地说是GF(2)上的向量空间。线性基B就是这个空间的一组“基”它需要满足两个核心性质线性无关性基B中的任何一个数都不能由基中其他数通过异或运算得到。张成性原集合S中任何一个数都可以由基B中的若干个数通过异或运算得到。这意味着什么意味着我们用线性基B完全“代表”了原集合S在异或运算下的所有可能性。B的大小即基向量的个数就是这个向量空间的维度。对于一个64位整数集合无论S有多大十万、百万它的线性基最多只有64个数。所有关于S的异或问题我们都可以在这至多64个数的小集合上高效解决。2.1 线性基的构建贪心与高斯消元思想的结合最常见的构建方法是“贪心法”它逐个数地尝试插入到基中。我们维护一个数组base[64]对于64位整数base[i]表示最高位为第 i 位的基向量。初始时base数组全为0。插入一个数x的过程如下从高位向低位遍历x的每一个为1的比特位i。如果base[i] 0那么我们将x赋值给base[i]插入完成。如果base[i] ! 0那么我们就用x异或上base[i]即x ^ base[i]然后继续尝试用新的x向下一位插入。这个过程的本质是动态维护一个上三角矩阵。每次遇到base[i]不为空就用已有的基去消掉当前数x的第i位试图将x化简。如果最终x被消成了0说明x可以由已有的基线性表出无需插入否则x最终会找到一个为空的base[j]安家成为新的基向量。为什么这样做是对的这其实是一个在线的高斯消元过程。base[i]存储的是当前已构建的基中最高位唯一为 i的那个向量。这个性质保证了基的线性无关性因为每个base[i]的最高位1的位置都不同那么任何一个base[i]都不可能由其他base[j]j ! i异或得到因为异或无法消除那个最高位的1。同时通过不断用已有的基去消元我们确保了新插入的数要么被已有的基表示冗余要么成为一个新的、最高位独特的基向量。注意这里说的“最高位”通常指二进制下最左边的1的位置例如数(10110)_2的最高位是第4位从0开始计数。在代码中我们常用(x i) 1来判断第i位是否为1用while (x)循环和右移操作来从低到高或从高到低遍历比特位。构建时从高到低遍历是为了优先保证“最高位唯一”的性质。2.2 一个完整的构建示例假设我们要将集合{4, 8, 10, 2}插入线性基。数字用二进制表示4 -01008 -100010-10102 -0010我们模拟base[4]数组索引0到3的构建过程插入4(0100)最高位是第2位。base[2]为空直接放入。base [0, 0, 4, 0]插入8(1000)最高位是第3位。base[3]为空直接放入。base [0, 0, 4, 8]插入10(1010)最高位是第3位。base[3]8(1000) 非空执行10 ^ 8 2(0010)。新的数2最高位是第1位。base[1]为空放入。base [0, 2, 4, 8]插入2(0010)最高位是第1位。base[1]2非空执行2 ^ 2 0。x变为0插入失败说明2已经可以由基{2,4,8}表示事实上2本身就在基中。最终线性基为{2, 4, 8}。原集合{4,8,10,2}的所有异或组合等价于{2,4,8}的所有异或组合。你可以验证10可以由2 ^ 8得到。3. 线性基的四大基础操作与代码实现理解了原理我们来看线性基最核心的四个操作插入、求最大值、查询存在性、求第k小值。我会给出清晰的代码和每一步的意图解释。3.1 操作一插入Insert这是所有操作的基础。代码实现如下以C为例处理63位以内整数class LinearBasis { private: long long base[64]; // 存储基向量base[i]最高位为i public: LinearBasis() { memset(base, 0, sizeof(base)); } bool insert(long long x) { for (int i 63; i 0; --i) { // 从高位向低位遍历 if (!(x i)) continue; // 如果x的第i位为0跳过 if (!base[i]) { base[i] x; // 找到空位插入 return true; // 插入成功 } x ^ base[i]; // 用已有的基消去x的第i位 } return false; // x被消成0插入失败说明x已能被表示 } };关键点解析for (int i 63; i 0; --i)从高位到低位检查这是保证“最高位唯一”性质的关键。if (!(x i)) continue;这是一个小优化如果x的第i位是0直接跳过避免无意义的判断。x ^ base[i];这是消元的核心步骤。因为base[i]的最高位是i所以这个操作一定能将x的第i位由1变为0。返回值bool很有用可以用于判断一个数是否与现有基线性相关返回false表示相关。3.2 操作二查询最大值Query Maximum给定线性基如何得到用这些基向量能异或出的最大值策略是贪心从高位到低位如果当前结果res异或上base[i]能变得更大就异或它。long long queryMax() { long long res 0; for (int i 63; i 0; --i) { // 如果res的第i位是0那么异或base[i]肯定能使res变大因为base[i]第i位是1 // 更稳健的写法直接判断 (res ^ base[i]) res if ((res ^ base[i]) res) { res ^ base[i]; } } return res; }为什么贪心是对的因为我们的基具有“最高位唯一”的性质。对于最高位i只有base[i]能提供这个位置的1。如果我们希望最终结果的第i位是1那么必须选择异或base[i]。从高位到低位决策优先保证高位是1结果自然最大。这是一种典型的“按位贪心”。3.3 操作三查询存在性Query Existence判断一个数x能否由线性基表示。方法就是尝试将x“插入”线性基但只进行消元不实际插入。如果最终x被消成0则表示存在。bool check(long long x) { for (int i 63; i 0; --i) { if (x i 1) { // 如果x的第i位是1 if (!base[i]) { return false; // 没有基可以消这个1说明无法表示 } x ^ base[i]; // 用base[i]消去x的第i位 } } return true; // x被消成0 }这个操作可以看作是插入操作的一个变体它回答了“给定一个数原集合中是否存在一个子集异或和等于它”的问题。3.4 操作四查询第k小值Query K-th Minimum这是线性基一个非常强大的功能。首先我们需要对线性基进行一步标准化处理称为“重建”或“规范化”。目标是让每个基向量base[i]除了最高位的1之外其他位尽可能都是0。这样基向量之间就几乎是“正交”的处理起来非常方便。重建过程如下void rebuild() { for (int i 63; i 0; --i) { for (int j i - 1; j 0; --j) { if (base[i] j 1) { // 如果base[i]的第j位是1 base[i] ^ base[j]; // 用低位的base[j]消去它 } } } // 将非零基向量紧凑存储到一个数组中方便处理 vectorlong long p; for (int i 0; i 63; i) { if (base[i]) p.push_back(base[i]); } // 此时p中的向量每个都只有最高位一个1其他位被消掉了 }重建后线性基的每个向量形如(1 i)即只有一位是1。那么所有能异或出的数就可以看作是对这些“位”的选择。如果我们把p中的向量按值从小到大排序那么第k小的异或值就对应于k的二进制表示中为1的那些位所对应的p中的向量进行异或。具体求法long long kthQuery(long long k) { // 假设已经rebuild并且结果存储在vectorlong long p中 if (p.size() n) { // 如果原集合能异或出0即存在线性相关 k--; // 因为最小的值0占了一个位置 } if (k (1LL p.size())) return -1; // k超出范围 long long res 0; for (int i 0; i (int)p.size(); i) { if (k i 1) { // 如果k的二进制第i位是1 res ^ p[i]; } } return res; }这里有两个至关重要的细节0的处理如果原集合的线性基大小p.size()小于原集合元素个数n说明存在线性相关那么异或空间里包含0一个都不选。0是最小的异或值。所以在排序时0占据了第1小的位置。因此当查询第k小时如果存在0我们需要将查询的k减1让出0的位置。k的范围p个线性无关的向量能产生2^p个不同的异或值包括0。所以有效的k范围是[1, 2^p]如果包含0。代码中k (1LL p.size())就是判断越界。4. 线性基的实战应用与变形掌握了基本操作我们来看看线性基在解决实际问题时的几种典型模式。很多题目不会直接问“求最大异或和”而是会披上各种外衣。4.1 模式一最大/最小异或路径问题描述给定一个无向连通图每条边有一个权值非负整数。求从节点u到节点v的所有路径中路径上边权异或和的最大值或最小值。关键转化这是一个经典问题。任意两点间的路径异或和等于它们各自到某个根节点比如1号节点的路径异或和的异或值。更具体地设dis[x]为从根到x的任意一条路径的异或和因为异或运算中环会被抵消。那么u到v的任意路径异或和都可以表示为dis[u] ^ dis[v] ^ (某个环的异或和)。因为u-v的路径可以拆成根-uu-vv-根而u-v和v-根可能形成环。解法以任意节点为根DFS或BFS求出每个节点i的dis[i]。找出图中所有的“简单环”或通过DFS树每条非树边对应一个环计算每个环的边权异或和。将这些环的异或值插入线性基。对于查询(u, v)答案就是(dis[u] ^ dis[v])与线性基能组合出的最大值用queryMax(dis[u] ^ dis[v])即初始值设为dis[u]^dis[v]再贪心。为什么环如此重要因为我们可以选择是否绕行一个环。从u到v的路径异或上任意一个环的异或值就得到了另一条u到v的路径。线性基的作用就是高效地管理这些“环权值”让我们能快速求出与某个初始值异或后的最大值。4.2 模式二带删除操作的线性基标准线性基只支持插入不支持删除。但在一些动态问题中我们需要处理元素的删除。有两种常见思路思路一离线处理 线段树分治如果所有操作插入和删除已知我们可以将每个元素的“存活时间”看作一个区间。利用线段树的结构将元素插入到线段树对应的区间节点上。最后遍历线段树进入节点时插入该节点上的所有元素离开节点时撤销回溯在叶子节点对应某个时间点回答查询。这需要线性基支持可撤销操作通常通过记录操作栈来实现。思路二带时间戳的线性基更通用维护线性基时不仅记录基向量base[i]还记录该基向量是由哪个元素或哪个时间点贡献的。当需要删除一个元素时如果它不在当前基中则无事发生如果它在基中情况就复杂了因为删除一个基向量可能会破坏整个基的结构。一种方法是找到另一个能代替它的向量在它之后插入的、同样能提供该最高位的向量来替换它。这需要更精巧的设计通常竞赛中更倾向于使用离线线段树分治的方法。4.3 模式三线性基求交与求并求并相对简单将两个线性基A和B中的所有基向量依次插入到一个新的线性基中即可。求交比较复杂。两个异或空间的交集本身也是一个异或空间。算法思想是设交集线性基为C。对于A中的每一个基向量v如果能被B的线性基和当前已构建的C表示出来那么v就属于交集空间或者更准确地说v能被B表示的部分属于交集。具体实现有几种方法一种常见的是维护一个“全能向量”w它由v和B中向量组合而成如果w能被A表示那么w就属于交集。求交的代码实现较为晦涩需要仔细理解向量空间的理论。在实际题目中求并的操作远多于求交。例如处理一棵树每个节点有一个权值查询某条路径上所有点权组成的集合的线性基即点权线性基的合并就可以用倍增或树剖预处理出路径上区间的线性基合并结果。5. 实现中的坑点、技巧与性能优化理论很美好但写代码时总会遇到一些坑。下面分享一些我踩过的雷和总结的经验。5.1 坑点一0 的特殊处理线性基是否包含“0”这个元素是很多问题的陷阱。何时存在0当插入的所有数线性相关时即存在一个非空子集的异或和为0。在代码层面当insert(x)返回false时就说明产生了线性相关此时异或空间包含0。对查询的影响最大值通常不影响因为0异或任何数等于其本身。最小值如果存在0那么最小值就是0否则最小值是所有基向量中最小的那个重建后就是最小的base[i]。第k小值如前所述如果存在00就是第一小查询时k需要减1。实战建议在解题时明确题目中“子集”是否允许为空集。如果允许空集异或和为0那么0就是一个合法值必须在考虑范围内。可以在线性基类中加一个bool zero_flag标记当有插入失败时将其置为true。5.2 坑点二long long 的位数与遍历顺序我们通常用for (int i 63; i 0; --i)来遍历64位有符号长整型。但这里有个细节long long的最高位第63位是符号位。如果我们处理的是非负整数这没有问题。但如果题目中数字可能有负数呢在异或运算的语境下数字是以补码形式存储的比特串。对于负数最高位是1。如果我们想求“最大异或和”并且数字可正可负那么贪心时从第63位开始看到符号位为1的基向量异或上它可能会得到一个很大的正数因为符号位被翻转也可能得到一个很小的负数。这时简单的(res ^ base[i]) res比较可能就不准确了因为它涉及有符号数的比较。一个更稳妥的写法是使用无符号类型unsigned long long或者非常小心地处理符号逻辑。建议如果题目明确说了是非负整数用long long和从63到0的遍历是安全的。如果存在负数最好统一使用unsigned long long来避免符号位的干扰或者仔细推导在符号位上的贪心策略是否依然成立有时题目性质保证了某种贪心依然有效。5.3 技巧一空间优化与位压存储标准的线性基需要O(bit_length)的空间对于64位是64个long long。如果位数很大比如处理位运算的位数达到几百或者需要同时维护很多个线性基比如线段树每个节点一个空间可能成为问题。一种优化技巧是使用位压bitset。例如在C中可以用std::bitset512来表示一个512位的向量。线性基的数组就变成bitset512 base[512]。插入、消元操作都通过bitset的位运算来完成。这样空间占用是O(bit_length^2 / word_size)但bitset操作是高效的。不过代码复杂度会上升。5.4 技巧二查询操作的常数优化在queryMax函数中我们通常用(res ^ base[i]) res来判断。这个判断本身有一次异或和一次比较。一个等价的写法是if ((res (1LL i)) 0) res ^ base[i];。即如果当前结果res的第i位是0就异或上base[i]因为base[i]的第i位肯定是1。这个写法少了一次异或运算在某些严格的卡常场景下可能有用但可读性稍差。对于check函数如果只是判断存在性我们也可以用一个“简化”版的插入提前返回false。5.5 性能考量预处理与查询的平衡线性基的构建是O(n * bit_length)单次查询最大、存在性是O(bit_length)第k小查询需要一次O(bit_length^2)的重建之后每次查询是O(bit_length)。在题目设计中通常n在1e5量级bit_length为64那么构建的1e5 * 64 ≈ 6.4e6次操作是完全可以接受的。如果需要处理海量查询1e6次那么O(bit_length)的单次查询也是高效的。需要警惕的是如果题目要求动态插入和查询第k小并且k每次变化那么每次查询前都可能需要rebuild这会导致O(q * bit_length^2)的复杂度对于q很大时可能超时。这种情况下可以考虑懒重建只有当基发生改变插入新元素后才标记需要重建在下次查询第k小时再真正执行重建。6. 从模板到精通理解线性基的本质最后我想分享一点超越代码模板的理解。线性基之所以强大是因为它将一个组合数学问题子集异或转化为了一个线性代数问题向量空间。这种转化带来了两个好处维度的压缩无论原集合多大有效信息被压缩到了至多“位数”个维度。这使得许多原本是指数复杂度的问题变成了多项式复杂度。结构的清晰基的“线性无关”和“张成”性质为我们提供了分析问题的清晰框架。求最大值时的贪心、求第k小时的二进制枚举都源于这个清晰的结构。当你下次遇到异或问题时不妨先问自己几个问题这个问题能被建模成在某个集合中选数异或吗这个集合是静态的还是动态的需要支持删除吗最终要查询的是什么最大值、最小值、第k小、还是存在性有没有可能通过预处理比如DFS求路径异或和、找环来构造出需要插入线性基的原始集合回答完这些问题该用线性基的哪种模式代码该怎么写心里就大致有数了。再结合上面提到的坑点和技巧就能写出既正确又高效的代码。线性基不是一个需要死记硬背的“黑盒”理解了它背后的线性代数思想你就能灵活地运用它甚至自己推导出它的各种变体和操作。这才是学习一个算法的正确方式。