注：线性基应当属于线性代数范畴，但是其在算法竞赛中通常用于维护异或，所以将其放在数据结构中。

算法竞赛中的线性基一般只考虑异或线性基。

线性基简单来讲就是一个整数集合的异或意义下的极大线性无关组。

具体而言，对于给定集合 $A$，任意整数 $c={\oplus }_{i=1}^n{a}_i,a_i\in A$，若都存在 $c={\oplus }_{i=1}^m{b}_i,b_i\in B$，且 $|B|$ 最小，则 $B$ 称作 $A$ 的线性基。

从另一个角度来看，线性基将原集合的 $2^n$ 的状态缩小至 $2^m$，其中 $n$ 是集合大小，$m$ 是值域的二进制位数。

在具体实现上，将集合中的任一元素，视作一个 $1\times m$ 的元素为 01 的向量；将原集合视作一个 $n\times m$ 的 01 矩阵。

假设第一列是最高位。

构建：

高斯消元：

从最高位开始，对该矩形进行高斯消元，化简成最简型矩阵。

去掉全零行，最终形成的 $m^{\prime }\times m$ 的矩阵即为原集合的线性基。

任一能通过选择原矩阵若干行求异或和得到的向量，都能通过选择最终矩阵的若干行异或得到。

使用 bitset 维护，时间复杂度：$O(\frac{m^{2}n}{w})$。

点击展开代码

void build(int n, vector<int> &t) {
    a.resize(n);
    num.resize(64);
    this->n = n;
    for (int i = 1; i <= n; i++) {
        a[i - 1] = t[i];
    }
    int now = 63;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (a[j][now]) {
                swap(a[j], a[i]);
                break;
            }
        }
        if (!a[i][now]) {
            now--;
            if (now < 0)
                break;
            i--;
        } else {
            num[i] = now;
            for (int j = 0; j < n; j++) {
                if (j == i)
                    continue;
                if (a[j][now])
                    a[j] ^= a[i];
            }
            now--;
            if (now < 0)
                break;
        }
    }
}

贪心法：

按 $1\sim n$ 的顺序将每一个元素加入线性基，也就是在前 $i-1$ 个元素构建的线性基的基础上维护新的线性基。

实际上和高斯消元本质相同，加入 $x$ 时，从最高位到最低位枚举 $x$ 二进制中的 $1$，找到第一个没有被占用的位，$x$ 占用这一位。过程中如果某一位已经被占据，则 $x$ 异或上这一位对应的行。

时间复杂度：$O(\frac{m^{2}n}{w})$。

与高斯消元相比的优势有：

• 在线
• 支持回退
• 空间复杂度：$O(w)$

点击展开代码

void insert(int v) {
    for (int i = 63; i >= 0; i--) {
        if ((v >> i) & 1) {
            if (!a[i]) {
                a[i] = v;
                break;
            } else {
                v ^= a[i];
            }
        }
    }
}

虽然一般情况下，线性基会从最高位开始消元，但实际上，因为秩的大小不一定为 $n$，那么消元后的自由元取决于对哪些位进行了消元。

求子集异或和第 $k$ 大时，需要从最高位开始消元，此时自由元是最高的若干位。但若期望自由元是最低的若干位，那么应当从最低位开始消元。若每一位带有额外权值，应当按位的权值顺序消元。

性质：

注意 $0$ 的特判，需要结合题目如果不选任何数是否可以视作 $0$ 下文中，均去掉 $0$。

判断线性基是否可以形成 $0$，只要判断在线性基构建的过程中是否出现了全 $0$ 行即可。

最小值：

最后一行非零行表示的二进制整数。

最大值：

所有行异或起来表示的二进制整数。

第 $k$ 小/大

首先，线性基能表示的整数数量为 $2^{m^{\prime }}$，所以第 $k$ 大可以等价于求第 $2^{m^{\prime }}-k+1$ 小。

事实上，这和字典序第 $k$ 小是类似的。

贪心地，从第一行开始，选择了第 $i$ 行，会超过 $2^{m^{\prime }-i}$ 个整数，所以和 $k$ 比较即可判断是否应该选择第 $i$ 行。

若线性基可表示值域超过整型范围，则无法通过整数运算求解。

进一步地，实际上可以注意到，第 $k$ 小相当于是选择 $k$ 的二进制中的 $1$ 位对应的那些行。

时间复杂度：$O(m)$。

点击展开代码

int query_max() {
    int res = 0;
    for (int i = 0; i < n; i++)
        res ^= a[i].to_ullong();
    return res;
}
int query_min() { return a[n - 1].to_ullong(); }
int query_kth(int k) {
    int cnt = 0;
    int flag = 1;
    for (int i = 0; i < n; i++) {
        if (a[i].count())
            cnt++;
        else
            flag = 0;
    }
    int res = 0;
    int m = n - 1;
    for (int i = n - 1; i >= 0; i--)
        if (a[i].count()) {
            m = i;
            break;
        }
    if (!flag) {
        k--;
    }
    if (!k)
        return 0;
    for (int i = 0; i < n; i++) {
        if ((k >> i) & 1)
            res ^= a[m - i].to_ullong();
    }
    return res;
}

解的构造

对于线性基找出的解，要还原出其在原集合中由哪些数组成。

set 维护

对于线性基过程中的每一个行向量，直接用一个 set 维护其由原序列中哪些数异或得到。

时间复杂度：$O(n{w}^2\log w)$。

点击展开代码

void insert(int x, int v) {
    set<int> now;
    now.insert(x);
    for (int i = 63; i >= 0; i--) {
        if ((v >> i) & 1) {
            if (!a[i]) {
                a[i] = v;
                pos[i] = now;
                break;
            } else {
                v ^= a[i];
                for (auto u : pos[i]) {
                    if (now.count(u))
                        now.erase(u);
                    else
                        now.insert(u);
                }
            }
        }
    }
}

时间复杂度证明在于线性基维护过程中，每个行向量最多由 $w$ 个原集合中的数异或得到。

bitset 维护

因为每个行向量由且仅有它前面的行向量异或得到，而行向量插入线性基后不会被覆盖，所以可以用一个 bitset 存储每一个行向量由当前哪些行向量异或得到，同时存下每个行向量插入线性基时初始对应的值。

还原元素时，把那些行向量的 bitset 异或起来，再把最终需要的行向量的初始值异或得到最后的解。

时间复杂度：$O(nw)$。

点击展开代码

void insert(int x, int v) {
    bitset<30> now;
    for (int i = 63; i >= 0; i--) {
        if ((v >> i) & 1) {
            if (!a[i]) {
                a[i] = v;
                mp[i] = x;
                pos[i] = now;
                pos[i].set(i);
                break;
            } else {
                v ^= a[i];
                now ^= pos[i];
            }
        }
    }
}

线性基的合并

即求 $\text{span}(A)\cap \text{span}(B)$ 和 $\text{span}(A)\cup \text{span}(B)$。

线性基的并

把 $\text{span}(A)$ 和 $\text{span}(B)$ 的每一个基向量插入即可。

时间复杂度：$O(w^2)$。

线性基的交

构建增广矩阵：$\left[\begin{array}{cc}A& 0\\ B& B\end{array}\right]$

其中 $A,B$ 是需要求交的线性基。

对于增广矩阵，进行高斯消元，最后得到行最简型矩阵。

系数矩阵中的零行对应的右侧行向量就是 $\text{span}(A)\cap \text{span}(B)$。

时间复杂度：$O(w^2)$。

点击展开代码

LinearBasis intersection_basis(LinearBasis &A, LinearBasis &B)
{
    struct Node
    {
        ull x, tag;
    };

    Node q[w + 1];
    for (int i = 0; i <= w; i++)
        q[i] = {0, 0};

    auto insert_aug = [&](ull x, ull tag, LinearBasis *ans)
    {
        for (int i = w; i >= 0; i--)
        {
            if (((x >> i) & 1) == 0)
                continue;

            if (!q[i].x)
            {
                q[i] = {x, tag};
                return;
            }

            x ^= q[i].x;
            tag ^= q[i].tag;
        }

        if (ans && tag)
            ans->insert(tag);
    };

    for (ull x : A.vectors())
    {
        insert_aug(x, 0, nullptr);
    }

    LinearBasis ans;
    for (ull x : B.vectors())
    {
        insert_aug(x, x, &ans);
    }

    return ans;
}

不同的线性基构造

高位线性基

优先保证高位消元成主元。

点击展开代码

低位线性基

与高位线性基相对，优先消低位。

但是因为整数的大小比较从高位开始，所以低位线性基无法做到与大小相关的操作。

一般不怎么使用。

任意主元顺序

更一般地，如果题目有相应的约束要求，可以按照任意顺序消主元。

最简线性基 / 规范线性基

前面朴素维护的高位/低位线性基，本质是行阶梯型的线性基，对于不同的插入顺序，得到的线性基也可能不同。

但是最简线性基唯一。

主要用于线性基去重 / 判断本质相同时使用。

本质是用高斯消元消成的行最简型。

可以由任一线性基通过高斯消元得到，时间复杂度：$O(w^2)$。

也可以直接在插入时维护行最简型。

点击展开代码

区间线性基

线段树维护

线段树上每个节点维护一个线性基，push_up 合并两个线性基。

预处理时间复杂度：$O(n{w}^2)$。

查询合并 $O(\log n)$ 个线性基，时间复杂度：$O(\log n{w}^2)$。

空间复杂度：$O(nw)$。

支持修改，时间复杂度：$O(q\log n{w}^2)$。

点击展开代码

ST 表维护

每次需要合并两个线性基，预处理时间复杂度：$O(n\log n{w}^2)$。

空间复杂度：$O(n\log nw)$。

查询合并两个线性基，时间复杂度：$O(q{w}^2)$。

相交猫树没有时空优势，唯一优势是好写。

点击展开代码

猫树维护

因为猫树是向线性基中加入元素，所以单次操作是 $O(w)$ 的。

猫树共有 $O(n\log n)$ 次插入，预处理时间复杂度：$O(n\log nw)$。

查询合并两个线性基，时间复杂度：$O(q{w}^2)$。

共存 $O(n\log n)$ 个线性基，空间复杂度：$O(n\log nw)$。

点击展开代码

前缀线性基

前缀的本质不同线性基只有 $O(w)$ 个。

维护 $[1,i]$ 的 $O(w)$ 个本质不同线性基，记录每个线性基的最后一个左端点的位置。

查询 $[l,r]$ 的线性基的时候，只要 $[1,r]$ 的找到第一个 $\ge l$ 的线性基即可。

预处理时间复杂度：$O(n{w}^2)$。

询问时间复杂度：$O(\log w)$，一般 $O(w)$ 即可。

空间复杂度：$O(n{w}^2)$。

优化

实际上，可以发现如果新插入的元素改变了线性基，在不化成行最简型的情况下，只会改变一个行向量。

那么每一个行向量尽可能用最靠后的元素。

处理 $[l,r]$ 的线性基时，就是在 $[1,r]$ 的线性基中保留 $\ge l$ 的行向量。

如果是高位线性基，那么需要替换能够替换的最高位。否则得到的可能是一个任意主元线性基。

时间复杂度：$O(nw+qw)$。

空间复杂度：$O(nw)$。

点击展开代码

分块维护

序列分块

维护 $O({\displaystyle \frac{n}{B}})$ 个整块线性基，查询时，合并 $O({\displaystyle \frac{n}{B}})$ 个线性基和加入 $O(B)$ 个元素。

时间复杂度：$O({\displaystyle \frac{qn}{B}}{w}^2+qBw)$。

空间复杂度：$O({\displaystyle \frac{n}{B}}w)$。

$n,q$ 视作同阶，最优时间复杂度：$O(n\sqrt{n}{w}^{\frac{3}{2}})$。

时间复杂度较劣，优势是空间优秀。

点击展开代码

在线莫队

预处理 $O({\displaystyle \frac{n}{B}}\times {\displaystyle \frac{n}{B}})$ 个线性基。

询问时，加入 $O(B)$ 个元素。

时间复杂度：$O(qBw+q{w}^2+{\displaystyle \frac{n^2}{B^2}}{w}^2)$。

空间复杂度：$O({\displaystyle \frac{n^2}{B^2}}w)$。

$n,q$ 视作同阶，块长取 $O((nw{)}^{\frac{1}{3}})$ 时，时间复杂度最优：$O((nw{)}^{\frac{4}{3}}+n{w}^2)$。

此时，空间复杂度为：$O(n^{\frac{4}{3}}{w}^{\frac{1}{3}})$。

点击展开代码

实现对比

下表中，$n$ 表示序列长度，$q$ 表示询问数，$w$ 表示值域二进制位数，$B$ 表示块长。

实现	预处理时间	单次询问时间	$q$ 次询问总时间	空间复杂度	优点	缺点 / 适用场景
线段树维护	$O(n{w}^2)$	$O(\log n{w}^2)$	$O(q\log n{w}^2)$	$O(nw)$	通用性最好，支持单点修改，空间只多一个线段树常数。	静态询问下时间不占优，每次查询要合并 $O(\log n)$ 个线性基。
ST 表维护	$O(n\log n{w}^2)$	$O(w^2)$	$O(q{w}^2)$	$O(n\log nw)$	思路和实现简单，两个重叠区间的线性基合并即可。	只支持静态序列；相比猫树，预处理更慢、空间相同、询问不更优。
猫树维护	$O(n\log nw)$	$O(w^2)$	$O(q{w}^2)$	$O(n\log nw)$	静态区间询问较适合，预处理只需要不断插入元素，比 ST 表少一个 $w$。	空间较大；不支持修改；询问仍要合并两个线性基。
前缀线性基	$O(n{w}^2)$	$O(\log w)$ 或 $O(w)$	$O(q\log w)$ 或 $O(qw)$	$O(n{w}^2)$	查询很快，利用前缀本质不同线性基只有 $O(w)$ 个。	空间较大，实现需要维护每个前缀的多个本质不同线性基；只适合静态序列。
前缀线性基优化	$O(nw)$	$O(w)$	$O(qw)$	$O(nw)$	静态区间询问通常最优秀，时空都接近最优，实现好后常数也小。	需要维护“每个主元尽量靠后”的位置约束；不如线段树通用，不能直接支持修改。
序列分块	$O(nw)$	$O({\displaystyle \frac{n}{B}}{w}^2+Bw)$	$O({\displaystyle \frac{qn}{B}}{w}^2+qBw)$	$O({\displaystyle \frac{n}{B}}w)$	空间最省，块内暴力加入元素即可；需要时可以重构单块支持修改。	查询较慢，块长需要调参；当 $n,q$ 同阶时最优仍为 $O(n\sqrt{n}{w}^{\frac{3}{2}})$。
在线莫队	$O({\displaystyle \frac{n^2}{B^2}}{w}^2)$	$O(Bw+w^2)$	$O(qBw+q{w}^2+{\displaystyle \frac{n^2}{B^2}}{w}^2)$	$O({\displaystyle \frac{n^2}{B^2}}w)$	查询不用删除元素，适合静态且询问较多的场景；可在线回答询问。	预处理和空间压力较大，块长需要平衡；当 $n,q$ 同阶时取 $B=O((nw{)}^{\frac{1}{3}})$ 才较优。

处理线性基的不可删

线性基容易维护加入一个元素，但是不容易维护删除一个元素。

线段树直接维护

开一棵大小是 $O(q)$ 的线段树维护即可。

时间复杂度：$O(q\log q{w}^2)$。

线段树分治

插入线性基时，如果按行阶梯型插入，只会修改 $O(1)$ 的位置，如果按行阶梯型插入，只会修改 $O(w)$ 的位置。

说明操作是可以暴力撤销的。

使用线段树分治 + 撤销栈，时间复杂度：$O(n\log nw)$，瓶颈是插入，所以撤销是 $O(1)$ 还是 $O(w)$ 影响不大。

空间复杂度：$O(q+w)$。