$介绍$

线性基通常用来解决异或类问题，

对于 $n$ 个数 $a_1, a_2, a_3, … , a_n (1\leq a_i\leq V)$，假设 $S = \{ \oplus_{x\in T} a_x \mid T \subseteq \{1, 2, …, n\}\}$，也就是从这 $n$ 个数中选出若干个异或起来能得到的数的集合。

那么它的线性基就是包含 $O(\log V)$ 个数的集合，设 $S’$ 表示从中选出若干个数异或起来得到的数的集合，那么满足 $S’ = S$。

$构造$

若现在给定 $n$ 个数 $a_1, a_2, a_3, … , a_n$ ，那么如何构造出它的一组线性基呢？

一组线性基可以表示为 $T = \{ t_1, t_2, … , t_{\log V} \}$，其中的每一位要么为 $0$，要么为二进制下最高位为 $i$ 的数。

空集的线性基为 $T = {0}$。

如果我们已知 $a_1, a_2, a_3, … , a_{n - 1}$ 的线性基 $t$，那么加入 $a_n$ 至线性基的流程如下

function insert(x:integer)
    for i := 30 downto 0 do
        if t[i] > 0 then
            x := x ^ t[i]
        else
        {
            t[i] := x
            break
        }
end function

要证明 $T$ 是 $a_1, a_2, a_3, … , a_n$ 的线性基，只需两点：

• $a$ 中的每一个数都能由 $T$ 中若干个数异或得到
• $T$ 中的每一个数都能由 $a$ 中若干个数异或得到

首先 $T$ 和加入 $a_n$ 之前的 $T’$ 相比相当于在原先为 $0$ 的位置上加了某个数 $x$ 或不变。

既然 $a_i(1 \leq i < n)$ 能由于 $T’$ 中若干数异或得到，同样能由 $T$ 中若干个数异或得到。

然后考虑 $a_n$ 是否能由 $T$ 得到，根据插入操作的伪代码，显然是可以得到的。

接下来考虑 $T$ 中的数是否都能由 $a$ 中若干个数异或得到，同理只要考虑新加入的数 $x$，

$x$ 可以表示为 $a_n$ 异或上若干个 $t_i$，而这若干个 $t_i$， 每一个都一定可以被 $a_1, a_2, … , a_{n - 1}$ 中的数异或得到，故 $T$ 一定为 $a_1, a_2, … , a_n$ 的线性基。

单次加入的时间复杂度 $O(\log V)$。

$查询最大值$

在一个集合能选出任意个数，使得异或起来后和给定的 $v$ 再异或的值最大，求这个最大值。

由于线性基满足 $t_i$ 上的数要么为 $0$，要么为二进制下最高位为 $i$ 的数，所以贪心从高位到低位取。

时间复杂度 $O(\log V)$

int qry(int x) {
    for (int i = 30; i >= 0; i -- )
        if (!(x >> i & 1)) {
            x ^= a[i];
        }
    return x;
}

$合并$

暴力的将一个线性基里的数加入到另一个线性基，时间复杂度 $O(\log^2 V)$

LineBase merge(LineBase A, LineBase B) {
    for (int i = 30; i >= 0; i -- )
        if (B.a[i]) A.add(B.a[i]);
    return A;
}

$性质$

1.如果现在给你一个线性基，将其中一个数变为与线性基内另一个下标小于它的元素的异或和，那么就得到了一个不同的满足要求的线性基。

2.如果将线性基进行如下操作

function exchange(x:integer)
    for i := 30 downto 0 do
        for j := i - 1 downto 0 do
            if t[i] & (1 << j) then 
                t[i] := t[i] ^ t[j]
end function

那么就可以得到一个线性基，满足其中任意两个数的与运算均为 $0$。

3.每一个可以由异或得到的数 $v$ 出现次数均为 $2^{n-len} (len 为线性基长度)$

证明：由于 $n$ 个数取若干个可以得到的不同的数是固定的，所以线性基长度是固定的。

称 $a_1, a_2, … , a_n$ 中的数在线性基中，当且仅当在加入它时执行了赋值操作。

所以 $a$ 中有 $len$ 个数在线性基中，观察这 $len$ 个数，发现将它们组合在一起同样可以组成一个线性基。

在剩下的 $n - len$ 个数中随便选，并且异或起来得到 $2^{n-len}$ 个数，设得到了 $x$，那么对于每一个 $v$，在存在于线性基中的 $len$ 个数一定可以有异或和为 $v \oplus x$ 的若干个数，所以对于每一个 $v$，都有 $2^{n-len}$ 种选择，证毕。

$求第 k 小异或值$

注意这里的第 $k$ 小指的是不重的第 $k$ 小。

先由性质 $2$ 改造线性基，再把为 $0$ 的位去掉。

于是如果 $k = (11100010)$，那么就是求 $base_1 \oplus base_5 \oplus base_6 \oplus base_7$，对应位异或起来即可。

int get_rk(int x) {
    vector<int> v;
    for (int i = 0; i < 31; i ++ ) //改造线性基
        if (a[i] > 0)
            v.push_back(i);
    int res = 0;
    for (int i = 0; i < v.size(); i ++ )
        if (x >> v[i] & 1)
            res += 1 << i;
    return res;
}

$时间戳线性基$

实现加入一个数，查询后缀线性基。

加入时强行将之前加入的与当前的交换，代码如下：

void insert(int x) {
    ++ tt;
    int id = tt;
    for (int i = 30; i >= 0; i -- )
        if (x >> i & 1) {
            if (!a[i]) a[i] = x, b[i] = id;
            else if (b[i] < id) {
                swap(a[i], x);
                swap(b[i], id);
            }
            x ^= a[i];
        }
}

目的是让时间戳小的依赖时间戳大的，从而做到能查询后缀线性基。

$练习题$

线性基练习题