线性基可用来解决子集异或之类的题目，我半夜看网课横竖睡不着，才发现 PPT 写满了 “线性代数”。

一。定义

这里我们定义一个数集 A 的 张成 Span(A) 为 A 中任意元素相互 异或 所组成的集合，线性无关 为数集中任意子集的异或和非 0；而对于一个数集 A，B 为其线性基当且仅当 B 是 A 的基。

学过线代我们知道，B 是 A 的基当且仅当：（1）B 可张成 A；（2）B 线性无关。既然如此，A 中任意元素可以被 B 唯一表示。

二。构造

我们设 did_i 表示线性基中最高位为 i 的数，那我们对于原数集中的每一个数 aia_i 重复以下操作：

  • 从高位到低位扫描 aia_i，若第 x 位非 0，则判断线性基中是否已经存在对应的 dxd_x；
  • 若不存在则令 dx=aid_x = a_i，否则 ai=ai⊕(1<<x)a_i = a_i \oplus (1<<x)，继续扫描；

伪代码：

void insert(int x)
{
    for (i: MaxBit -> 0) {
        if (Not_exit(x,i)) continue;
        if (!d[i]) { d[i] = x; break; }
        x ^= (1<<i);
    }
}

代码短小精悍，但有一个缺陷，这组基并非是正交的，即我们想要一组线性基满足：第 i 位仅存在于 did_i 中.

可以参考 Menci 的博客，简单来说对于插入 did_i 的过程，我们要满足：

  • 当前元素 x 插入 did_i 后，已存在于线性基中 的更低位为 0；
  • 当前元素 x 插入 did_i 后，线性基中高位 djd_j 的第 i 位为 0；

加两重循环判断一下即可，这种插入手段时间复杂度也是 O(logx) ?

代码：

void insert(ll x)
{
    for (int i = MAXL; j >= 0; j++) {
        if ((t & (1<<i)) == 0) continue;
        if (d[i]) {x ^= d[i]; continue;}
        for (int k=0; k<i; k++) if (x & (1<<k)) x ^= d[k];
        //必须拿内部的元素异或 x 而不是 1<<k ，以满足空间的封闭性
        //你管他 d[k] 是不是 0 
        for (int k=i+1; k<= MAXL; k++) 
            if (d[k] & (1<<i)) d[k] ^= x;
        //必须拿 x 异或 d_k，以满足空间的封闭性
        d[i] = x; return;
    }
}

三。应用

线性基的应用巨多，只要和异或有关系都可以往上面靠一靠。

1. 求异或最值

若是集合内 两个数 的异或最值，可以试试 01Trie 树，建好树后贪心逆着走就行。

对于集合内 任意数 的异或最值，由于线性基和原集合等价，而最高位 did_i 不会出现重复，则异或最小值就是线性基中的最小值，异或最大值就是线性基全异或起来。

2. 求异或第 k 小 / 查询排名

其实可以感性理解，把 k 表示为二进制数，由于两者都单调递增，那如果 k 的第 i 位为 1，可以直接映射 did_i，查询的时候直接异或上就行了。

同理，查询排名可以类比二叉树，当前数 x 大于 d_i 就异或掉，并将排名加上 2i2^i 即可。