线性基

回想高中数学立体几何中基向量的概念，我们可以在三维欧氏空间中找到一组基向量，，，之后空间中任意一个向量都可以由这组基向量表示。换句话说，我们可以 通过有限的基向量来描述无限的三维空间，这足以体现基向量的重要性。

三维欧氏空间是特殊的线性空间，三维欧氏空间的基向量在线性空间中就被推广为了线性基。

OI 中有关线性基的应用一般只涉及两类线性空间：维实线性空间和维布尔域线性空间，我们会在应用一节中详细介绍。若您不熟悉线性代数，则推荐从应用部分开始阅读。

以下会从一般的线性空间出发来介绍线性基，并给出线性基的常见性质。

前置知识：线性空间。

线性基是线性空间的一组基，是研究线性空间的重要工具。

定义

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

规定线性空间的基为空集。

可以证明任意线性空间均存在线性基¹，我们定义线性空间的维数为线性基的元素个数（或势），记作。

性质

对于有限维线性空间 , 设其维数为 , 则：
1. 中的任意个向量线性相关。
2. 中的任意个线性无关的向量均为的基。
3. 若中的任意向量均可被向量组线性表出，则其是的一个基。
  
  证明
  
  任取中的一组基 , 由已知条件，向量组可被线性表出，故
  
  因此
4. 中任意线性无关向量组均可通过插入一些向量使得其变为的一个基。
（子空间维数公式）令是关于的有限维线性空间，且和也是有限维的，则

证明

设 ,,.

取的一组基 , 将其分别扩充为和中的基：和 .

接下来只需证明向量组线性无关即可。

设 .

则 .

注意到上式左边在中，右边在中，故两边均在中，因此

故 , 进而
令是关于的有限维线性空间，且和也是有限维的，则下列诸款等价：
1. .
2. .
3. 若是的一组基，是的一组基，则是的一组基。
Note

1,3 两条可推广到无限维线性空间中

例子

考虑的基。

如图

是一组基。
如图

是一组基。
如图

不是一组基，因为 .
如图

不是一组基，因为 .

正交基与单位正交基

若线性空间的一组基满足（即两两正交），则称这组基是 正交基。

若线性空间的一组正交基还满足，则称这组基是 单位正交基。

任意有限维线性空间的基都可以通过 Schmidt 正交化变换为正交基。

应用

根据前文内容，我们可以利用线性基实现：

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

在 OI 中，我们一般将维实线性空间下的线性基称为 实数线性基，维布尔域线性空间下的线性基称为 异或线性基。

Tip

中的加法为异或，乘法为与，可以证明是域。

可以证明代数系统是线性空间，其中：

即加法是异或，数乘是与。

以异或线性基为例，我们可以根据给定的一组布尔序列构造出一组异或线性基，这组基有如下性质：

中任意非空子集的异或和不为；
对中的任意元素，都可在中取出若干元素使其异或和为；
对任意满足上两条的集合，其元素个数不会小于的元素个数。

我们可以利用异或线性基实现：

判断一个数能否表示成某数集子集的异或和；
求一个数表示成某数集子集异或和的方案数；
求某数集子集的最大/最小/第大/第小异或和；
求一个数在某数集子集异或和中的排名。

构造方法

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

贪心法

对原集合的每个数转为二进制，从高位向低位扫，对于第位是的，如果不存在，那么令并结束扫描，如果存在，令。

查询原集合内任意几个元素的最大值，只需将线性基从高位向低位扫，若上当前扫到的答案变大，就把答案异或上。

为什么能行呢？因为从高往低位扫，若当前扫到第位，意味着可以保证答案的第位为，且后面没有机会改变第位。

查询原集合内任意几个元素的最小值，就是线性基集合所有元素中最小的那个。

查询某个数是否能被异或出来，类似于插入，如果最后插入的数被异或成了，则能被异或出来。

代码（洛谷 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;
}

高斯消元法

高斯消元法相当于从线性方程组的角度去构造线性基，正确性显然。

代码（洛谷 P3812 【模板】线性基）

#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;
}

性质

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

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

高斯消元法构造出的线性基满足如下性质：

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

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

如果不理解这条性质的正确性，可以跳转高斯消元。

提供一组样例：

5
633 211 169 841 1008

二进制表示：

贪心法生成的线性基：

高斯消元法生成的线性基：

这是一条非常好的性质，能帮我们更方便的解决很多问题。比如：给定一些数，选其中一些异或起来，求异或最大值，如果用贪心法构造线性基，需要再做一遍贪心，如果 ans 的当前位是 0，那么异或一定会更优，否则当前位如果为 1，则一定不会更优；而使用高斯消元法构造线性基后直接将线性基中所有元素都异或起来输出即可。

对于其他比较经典的问题（查询一个数能否被异或得到，查询能被异或得到的第大数等），高斯消元法得到的线性基也能更加方便地解决。

时间复杂度

设向量长度为 , 总数为 , 则时间复杂度为 . 其中高斯消元法的常数略大。

若是实数线性基，则时间复杂度为 .

线性基合并

线性基的合并只需要暴力处理，即将要合并的一组线性基暴力地插入到另一组线性基即可。单次合并的时间复杂度是（异或线性基）或（实数线性基）。

线性基求交

线性基求交，严格地说就是求它们张成的两个线性空间的交空间的一组线性基。本节介绍两种算法。这两种算法，单次求交的时间复杂度都是（异或线性基）或（实数线性基）。

朴素算法

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

将线性基中的向量利用贪心法尝试插入到中，并初始化线性基的交为空集；
在插入时，需要记录要插入的向量中，线性基中元素的贡献。具体地，维持一个新向量，初始化为，而且，如果正在插入的向量与线性基中第位的向量取了异或，那么贡献也要与第位记录的贡献取一次异或；
如果插入成功，在线性基的第位插入了向量，就将第位记录的改为得到的过程中线性基中元素的贡献；
如果插入不成功，就将过程中记录到的线性基中元素的贡献插入到中。

这样得到的线性基就是所求的交，当然，该算法同时也求出了线性基的并。

对算法的解释

设合并后的线性基为，其中，是插入时最后得到的向量。那么，同样是一组合并后的线性基。记为集合，则合并后的基可以写作。而且，和空间中的每个向量都可以唯一地表示成

的形式，其中，且。这个分解中的就是前文算法所试图记录的「线性基中元素的贡献」。严格地说，只是中最后成功插入的那些向量的贡献。

对于成功的插入，最后记录的就是该分解中的项。设。初始时，，已经是在基上的正确的分解。在更新为时，因为，所以，只需要更新为，就可以保证分解依然正确。因此，归纳可知，最后插入到合并后的线性基中时，记录的贡献就是上述分解中的项。

对于不成功的插入，最后要插入的变量一定会变成，而此时的贡献要插入到中。此时，如果重复上面的论证，会发现仍然能够保证在插入过程中总是有，且，只是不再属于。这是因为初始化时，中的。除此之外，贡献更新时异或的项都属于。所以，实际上，有。

那么，为什么将这些插入不成功时的都插入到中，就能得到交空间的线性基呢？首先，插入不成功，最后一定会得到，其中，且。因此，必然位于交空间中。反过来，设是交空间中的任意元素，因为，所以可以表示为中元素的线性组合（异或和）：

其中，。对于每一个，记相应的插入到中的贡献为，就有

注意到，和都位于交空间中，因而左侧必然也位于交空间中，故而左侧可以写成中元素的线性组合；同时，右侧所有项，要么，要么且，故而，右侧实际上是中元素的线性组合。但是，线性无关，故而所有的系数都是，也就是说。这就说明了，这些无法插入的向量的贡献共同张成了交空间。

根据这一解释，过程中维护贡献的目的，实际上是为了维护分解；而且，最后向插入贡献时也总有。所以，无论维护还是中元素的贡献（即无论维护还是），得到的结果都是正确的。如果要维护线性基中元素的贡献，只需要修改初始化时相应贡献的取值：每个中的向量初始就有贡献，而插入的初始贡献为。

模板题代码如下：

代码（Library Checker Intersection of

vector spaces）

#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 算法相当于维护中元素的贡献的朴素算法。如果转而先插入所有，再插入所有，那么基于贪心法的 Zassenhaus 算法就相当于维护中元素贡献的朴素算法。根据消元步骤的等价性，Zassenhaus 算法的正确性也是成立的。

除此之外，还可以再提供一个独立且更为一般的代数证明：

正确性证明

设为一线性空间，且有子空间和。算法本身相当于通过化简为行阶梯型来求子空间

的一组基。算法最后，中的元素根据与否需要分为两类，所以不妨考察投影映射且。于是，且容易验证

根据线性映射的相关定理，有。

行阶梯型矩阵的前几列仍然是行阶梯型矩阵，因而的行的数目，恰好等于的行秩，亦即；而且，这些行中的集合就形成了的一组基。剩下的非零行恰好有个，且都满足。对于这些行中的，因为有，所以；而且，作为行阶梯型矩阵的行，必然线性无关，这就说明这些都线性无关。综合起来，这些是交空间中大小为的线性无关组，所以也必然是该空间的一组基。

模板题代码如下：

代码（Library Checker Intersection of

vector spaces）

#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）

#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;
}

如果需要在线询问，也可以用的空间将每个前缀处的前缀线性基都存下来再查询，这可以看作是一种「可持久化」线性基。如果需要用到高斯消元法得到的线性基的性质，可以在查询时另行处理。

练习题

参考资料与注释

Proof that every vector space has a basis ↩

最后更新: 2025年4月6日
创建日期: 2018年7月11日