线性基
回想高中数学立体几何中基向量的概念，我们可以在三维欧氏空间中找到一组基向量 通过有限的基向量来描述无限的三维空间 ，这足以体现基向量的重要性。
三维欧氏空间是特殊的 线性空间 ，三维欧氏空间的基向量在线性空间中就被推广为了线性基。
OI 中有关线性基的应用一般只涉及两类线性空间：布尔域 线性空间 应用 一节中详细介绍。若您不熟悉线性代数，则推荐从应用部分开始阅读。
以下会从一般的线性空间出发来介绍线性基，并给出线性基的常见性质。
前置知识：线性空间 。
线性基是线性空间的一组基，是研究线性空间的重要工具。
定义
称线性空间 Hamel 基 或 线性基 ，简称 基 。
规定线性空间
可以证明任意线性空间均存在线性基维数 为线性基的元素个数（或势），记作
性质
对于有限维线性空间
若
证明
任取
因此
（子空间维数公式）令
证明
设
取
接下来只需证明向量组
设
则
注意到上式左边在
故
令
若
Note
1,3 两条可推广到无限维线性空间中
例子
考虑
如图
如图
如图
如图
正交基与单位正交基
若线性空间 正交基 。
若线性空间 单位正交基 。
任意有限维线性空间 Schmidt 正交化 变换为正交基。
应用
根据前文内容，我们可以利用线性基实现：
求给定向量组的秩；
对给定的向量组，找到一组极大线性无关组（或其张成的线性空间的一组基）；
向给定的向量组插入某些向量，在插入操作后的向量组中找到一组极大线性无关组（或其张成的线性空间的一组基）；
对找到的一组极大线性无关组（或基），判断某向量能否被其线性表出；
对找到的一组极大线性无关组（或基），求其张成的线性空间中的特殊元素（如最大元、最小元等）。
在 OI 中，我们一般将 实数线性基 ，异或线性基 。
Tip
可以证明代数系统
即加法是异或，数乘是与。
以异或线性基为例，我们可以根据给定的一组布尔序列
对
对任意满足上两条的集合
我们可以利用异或线性基实现：
判断一个数能否表示成某数集子集的异或和；
求一个数表示成某数集子集异或和的方案数；
求某数集子集的最大/最小/第
求一个数在某数集子集异或和中的排名。
构造方法
因为异或线性基与实数线性基没有本质差别，所以接下来以异或线性基为例，实数线性基版本的代码只需做一点简单修改即可。
贪心法
对原集合的每个数
查询原集合内任意几个元素
为什么能行呢？因为从高往低位扫，若当前扫到第
查询原集合内任意几个元素
查询某个数是否能被异或出来，类似于插入，如果最后插入的数
代码（洛谷 P3812 【模板】线性基 ）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 #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 ;
}
高斯消元法
高斯消元法相当于从线性方程组的角度去构造线性基，正确性显然。
代码（洛谷 P3812 【模板】线性基 ）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39 #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 ;
}
性质
贪心法构造的线性基具有如下性质：
线性基没有异或和为
线性基中各数二进制最高位不同。
高斯消元法构造出的线性基满足如下性质：
高斯消元后的矩阵是一个行简化阶梯形矩阵。
该性质包含了贪心法构造的线性基满足的两条性质
如果不理解这条性质的正确性，可以跳转 高斯消元 。
提供一组样例：
二进制表示：
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，则一定不会更优；而使用高斯消元法构造线性基后直接将线性基中所有元素都异或起来输出即可。
对于其他比较经典的问题（查询一个数能否被异或得到，查询能被异或得到的第
时间复杂度
设向量长度为
若是实数线性基，则时间复杂度为
线性基合并
线性基的合并只需要暴力处理，即将要合并的一组线性基暴力地插入到另一组线性基即可。单次合并的时间复杂度是
线性基求交
线性基求交，严格地说就是求它们张成的两个线性空间的交空间的一组线性基。本节介绍两种算法。这两种算法，单次求交的时间复杂度都是
朴素算法
设要求交的线性基分别是
将线性基 贪心法 尝试插入到
在插入时，需要记录要插入的向量中，线性基
如果插入成功，在线性基的第
如果插入不成功，就将过程中记录到的线性基
这样得到的线性基
对算法的解释
设合并后的线性基为
的形式，其中，试图 记录的「线性基
对于成功的插入，最后记录的
对于不成功的插入，最后要插入的变量一定会变成
那么，为什么将这些插入不成功时的
其中，
注意到，
根据这一解释，过程中维护贡献
模板题代码如下：
代码（Library Checker Intersection of ）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89 #include <array>
#include <iostream>
class LinearBasis {
static constexpr int K = 30 ;
std :: array < int , K > a ;
// Size of basis.
int size () const {
int res = 0 ;
for ( auto x : a ) {
if ( x ) {
++ res ;
}
}
return res ;
}
public :
LinearBasis () : a {} {}
// Insert vector x.
void insert ( int x ) {
for ( int k = K - 1 ; ~ k && x ; -- k ) {
if (( x >> k ) & 1 ) {
if ( ! a [ k ]) {
a [ k ] = x ;
}
x ^= a [ k ];
}
}
}
// 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 ;
}
// Output.
void print () const {
std :: cout << size ();
for ( auto x : a ) {
if ( x ) {
std :: cout << ' ' << x ;
}
}
std :: cout << '\n' ;
}
};
int main () {
int t ;
std :: cin >> t ;
for (; t ; -- t ) {
LinearBasis a , b ;
int n ;
std :: cin >> n ;
for (; n ; -- n ) {
int x ;
std :: cin >> x ;
a . insert ( x );
}
int m ;
std :: cin >> m ;
for (; m ; -- m ) {
int x ;
std :: cin >> x ;
b . insert ( x );
}
a . intersect ( b ). print ();
}
return 0 ;
}
Zassenhaus 算法
另一种等价的做法是 Zassenhaus 算法，它同样可以同时计算出两个线性基的并和交。复杂度和上文完全一致。
具体步骤如下：
初始化一个向量长度为
将
将
最后得到的线性基
算法中的构造线性基的方法可以是 贪心法 或 高斯消元法 ，只要保证
将 Zassenhaus 算法中的消元的步骤与上面的朴素算法相比较，很容易发现，基于贪心法的 Zassenhaus 算法相当于维护
除此之外，还可以再提供一个独立且更为一般的代数证明：
正确性证明
设
的一组基
根据 线性映射的相关定理 ，有
行阶梯型矩阵的前几列仍然是行阶梯型矩阵，因而
模板题代码如下：
代码（Library Checker Intersection of ）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64 #include <iostream>
#include <vector>
class LinearBasis {
int K ;
std :: vector < long long > a ;
public :
LinearBasis ( int K ) : K ( K ), a ( K ) {}
// Insert vector x.
void insert ( long long x ) {
for ( int k = K - 1 ; ~ k && x ; -- k ) {
if (( x >> k ) & 1 ) {
if ( ! a [ k ]) {
a [ k ] = x ;
}
x ^= a [ k ];
}
}
}
// Output those not exceeding 2^k.
void print ( int k ) const {
int sz = 0 ;
for ( int i = 0 ; i < k ; ++ i ) {
if ( a [ i ]) {
++ sz ;
}
}
std :: cout << sz ;
for ( int i = 0 ; i < k ; ++ i ) {
if ( a [ i ]) {
std :: cout << ' ' << a [ i ];
}
}
std :: cout << '\n' ;
}
};
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 );
}
int m ;
std :: cin >> m ;
for (; m ; -- m ) {
int x ;
std :: cin >> x ;
c . insert (( long long ) x << K );
}
c . print ( K );
}
return 0 ;
}
注意，输出时只需要考虑前
拓展：前缀线性基
本节只讨论异或线性基的情形，并假设单个向量可以存储在
对于需要多次查询区间异或最大值的情形，一种常见的做法是 猫树 配合线性基，时间复杂度为
前缀线性基允许对于序列的每个前缀，都维护该前缀的所有后缀的线性基，这样就可以支持查询每个区间的线性基。注意到序列的某个前缀
不妨将每个向量
这个表达式不过是将上一段的叙述用形式的语言写出来而已。它给我们带来的启发是，要维护线性基中每个向量
基于上文提到的 贪心法 构造线性基，前缀线性基在构造过程中做了如下调整：
为线性基中保留的每个向量
要添加序列中第
如果
如果
如果
也就是说，如果当前位可以通过较新的向量表示，就直接用较新的向量；否则，保留原来的向量。在更新位置 高斯消元法 构造线性基的过程中向上更新时可能会破坏时间戳的性质，所以不再适用于构造前缀线性基。
模板题代码如下：
代码（Codeforces 1100F Ivan and Burgers ）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62 #include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <vector>
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 ;
}
};
int main () {
int n ;
std :: cin >> n ;
std :: vector < int > c ( n + 1 );
for ( int i = 1 ; i <= n ; ++ i ) std :: cin >> c [ i ];
int q ;
std :: cin >> q ;
std :: vector < std :: array < int , 2 >> qu ( q );
for ( auto & v : qu ) std :: cin >> v [ 0 ] >> v [ 1 ];
std :: vector < int > ids ( q );
std :: iota ( ids . begin (), ids . end (), 0 );
std :: sort ( ids . begin (), ids . end (),
[ & ]( int l , int r ) -> bool { return qu [ l ][ 1 ] < qu [ r ][ 1 ]; });
LinearBasis lb ;
std :: vector < int > res ( q );
for ( int i = 1 , j = 0 ; i <= n ; ++ i ) {
lb . insert ( c [ i ], i );
for (; j < q && qu [ ids [ j ]][ 1 ] == i ; ++ j ) {
res [ ids [ j ]] = lb . query ( qu [ ids [ j ]][ 0 ]);
}
}
for ( int x : res ) std :: cout << x << '\n' ;
return 0 ;
}
如果需要在线询问，也可以用
练习题
参考资料与注释
丘维声，高等代数（下）。清华大学出版社。
Basis (linear algebra) - Wikipedia Vector Basis -- from Wolfram MathWorld Zassenhaus algorithm - Wikipedia
2025/4/1 23:27:00 ，更新历史 在 GitHub 上编辑此页！ cesonic , Enter-tainer , Great-designer , Ir1d , ksyx , lychees , MegaOwIer , RUIN-RISE , Tiphereth-A , wjy-yy , aofall , c-forrest , CoelacanthusHex , iamtwz , Marcythm , Menci , ouuan , Persdre , rsdbkhusky , shuzhouliu , Xeonacid CC BY-SA 4.0 和 SATA
