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

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

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

具体而言，对于给定集合 $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^{rank}$，其中 $n$ 是集合大小，$rank$ 是线性基的秩。

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

假设第一列是最高位。

构建：

高斯消元：

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

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

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

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

点击展开代码

void build(int n, vector<u64> &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(nw)$。

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

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

点击展开代码

void insert(u64 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$ 当且仅当输入向量线性相关，也就是 $\mathrm{rank}<n$；输入中含有 $0$ 是其中一种情况。增量插入时，某个原向量被当前基约化为 $0$，或批量高斯消元后出现全零行，都说明输入线性相关。实现中应单独记录这个标志；去掉全零行后的线性基本身仍然是线性无关的。

---

下面关于“最后一行”、“所有行异或”和“下标二进制位对应基向量”的结论，都要求线性基已化为高位主元的行最简形：每个主元位只在它所在的基向量中为 $1$，且非零行按主元从高到低排列。前面从高位开始的完整高斯消元可得到这种规范基；朴素贪心 insert 通常只得到行阶梯形，查询前还需进一步消元。

最小值：

若允许空集，最小值始终是 $0$。若要求子集非空，输入线性相关时最小值也是 $0$；输入线性无关时，在上述规范基中，最后一个非零行才是最小的正异或值。对普通行阶梯基不能直接使用“最后一行”这个结论。

最大值：

在上述规范基中，所有非零行的异或和是最大值。对普通行阶梯基，应从高位主元到低位主元扫描，只在 res ^ basis[i] > res 时更新 res；直接异或所有行不一定正确。

第 $k$ 小/大

设线性基的秩为 $r$，则共有 $2^r$ 个不同的可表示值。先将规范基的非零行改按主元从低到高记为 $b_0,b_1,\dots ,b_{r-1}$。对于 $0\le t<2^r$，定义

$$F(t)=\underset{\begin{array}{c}0\le i<r\\ {\mathrm{bit}}_i(t)=1\end{array}}{⨁}{b}_i$$

此时 $F(0),F(1),\dots ,F(2^r-1)$ 恰好按数值从小到大排列。因此，若用从 $1$ 开始的 $k$ 且把 $0$ 算在答案中，第 $k$ 小是 $F(k-1)$。若只允许非空子集，输入线性相关时仍包含 $0$；输入线性无关时需排除 $F(0)$，此时第 $k$ 小是 $F(k)$。第 $k$ 大应先按当前约定确定答案总数 $M$，再转换为第 $M-k+1$ 小。

“把下标的二进制 $1$ 位直接对应到基向量”只对上述规范基和排列顺序成立；普通行阶梯基必须先化为行最简形。规范化需要 $O(w^2)$ 时间，之后单次查询需要 $O(r)$ 时间。计算 $2^r$ 和查询下标时还需使用足够宽的无符号整数，并避免对整型位宽执行移位。

下面的查询代码沿用“非零行按主元从高到低排列，全零行位于末尾”的存储约定，其中 query_min 和 query_kth 按“子集必须非空”处理 $0$。

点击展开代码

u64 query_max() {
    u64 res = 0;
    for (int i = 0; i < n; i++)
        res ^= a[i].to_ullong();
    return res;
}
u64 query_min() { return a[n - 1].to_ullong(); }
u64 query_kth(u64 k) {
    u64 cnt = 0;
    bool flag = 1;
    for (int i = 0; i < n; i++) {
        if (a[i].count())
            cnt++;
        else
            flag = 0;
    }
    u64 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 维护其由原序列中哪些下标异或得到。设最终线性基的秩为 $r$，则 $r\le w$。

点击展开代码

void insert(int x, u64 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);
                }
            }
        }
    }
}

这份增量实现只会把“使秩增加”的输入下标保存到 pos。被当前线性基约化为 $0$ 的输入不会写入任何 pos[i]，因此所有已保存的来源下标都属于至多 $r$ 个独立输入，单个 pos[i] 的大小为 $O(r)$，不会在该不变量下增长到 $O(n)$。

内层循环计算 now 与 pos[i] 的集合对称差。一次 count、erase 或 insert 的代价是 $O(\log (r+1))$，但处理整个 pos[i] 需要

$$O(|pos[i]|\log (r+1))=O(r\log (r+1)),$$

而不是 $O(\log w)$。插入一个数需扫描 $w$ 个二进制位，并最多与 $r$ 个基向量做对称差，所以单次复杂度为

$$O(w+r^2\log (r+1)).$$

处理 $n$ 个输入的总时间复杂度为

$$O\left(n(w+r^2\log (r+1))\right)\subseteq O(n{w}^2\log (w+1)).$$

所有 pos 中保存的来源下标总数为 $O(r^2)$，计入 $w$ 个 set 对象的空间后为 $O(w+r^2)$。若改用不保持上述不变量的一般高斯消元来保存任意原始行组合，单个来源集合才可能增长到 $O(n)$。

bitset 维护

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

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

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

点击展开代码

void insert(int x, u64 v) {
    bitset<64> 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];
            }
        }
    }
}

线性基的合并

线性基可以用来求两个子空间的交，或者将两个子空间合并为它们的子空间和。

子空间和 / 线性基合并

令 $U=\mathrm{span}(A)$，$V=\mathrm{span}(B)$。集合并 $U\cup V$ 通常对异或不封闭，因此通常不是子空间；只有当 $U\subseteq V$ 或 $V\subseteq U$ 时，$U\cup V$ 才是子空间。

将 $A$ 和 $B$ 的基向量全部插入同一个线性基，得到的是子空间和

$$U+V=\{u\oplus v\mid u\in U,v\in V\}=\mathrm{span}(A\cup B),$$

而不是集合并 $U\cup V$。

时间复杂度：$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;
}

不同的线性基构造

高位线性基

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

点击展开代码

低位线性基

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

因为整数的大小比较从高位开始，低位线性基不能直接套用高位线性基的最大值贪心，但这不代表它无法回答与大小相关的查询。可以把其至多 $w$ 个基向量重新插入高位线性基，或者从高位开始重新消元，在 $O(w^2)$ 时间内得到高位基或规范基，之后可以在 $O(w)$ 时间内查询最大值。

因此，低位线性基只是不适合直接进行高位贪心，而不是丢失了原线性空间的信息。

任意主元顺序

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

最简线性基 / 规范线性基

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

但是最简线性基唯一。

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

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

可以由任一线性基通过高斯消元得到，时间复杂度：$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(\sqrt{nw})$。

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

点击展开代码

在线莫队

预处理 $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)$。

线段树分治

设时间轴上有 $q$ 个操作，共得到 $m$ 个元素的有效时间区间。每个时间区间需要拆到线段树的 $O(\log q)$ 个节点中，因此线段树上共存储 $O(m\log q)$ 个事件副本。

插入线性基时，普通行阶梯型实现只会修改至多一个主元位置，每次成功修改只需记录 $O(1)$ 个撤销信息；若始终维护行最简形，一次插入可能修改 $O(w)$ 个位置，需要记录对应的旧值。

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

普通线性基的一次插入需要 $O(w)$ 时间，因此使用线段树分治和撤销栈处理所有事件副本的时间复杂度为

$$O(mw\log q).$$

若在至多 $q$ 个叶子处各执行一次 $O(w)$ 的线性基查询，则算法的总时间复杂度为 $O((m\log q+q)w)$。

普通行阶梯型实现的空间复杂度为

$$O(m\log q+q+w),$$

其中 $O(m\log q)$ 是事件副本，$O(q)$ 是线段树节点，$O(w)$ 是当前线性基和撤销信息。通常 $m=O(q)$，此时总时间复杂度为 $O(qw\log q)$，空间复杂度为 $O(q\log q+w)$。若维护行最简形，当前 DFS 路径上的撤销记录最坏还可能需要 $O(w^2)$ 空间。