「算法学习」线性基及其进阶操作

到现在才发现，以前学过的线性基最多算个 🐘。

基本定义

线性基是向量空间的一个线性无关子集，……

定义说的实在不是人话，与其我们用复杂的语言去定义线性基是个什么东西，不如先来看看线性基的性质是什么。

线性基的性质

摘自维基百科的定义

设 $\mathfrak {B}$ 是向量空间 $\mathrm {V}$ 的子集。则 $\mathfrak {B}$ 是基，当且仅当满足了下列任一条件：

• $\mathfrak {B}$ 是 $\mathrm {V}$ 的极小生成集，就是说只有$\mathfrak {B}$能生成$\mathrm {V}$，而它的任何真子集都不能生成全部的向量空间。
• $\mathfrak {B}$是$\mathrm {V}$中线性无关向量的极大集合，就是说$\mathfrak {B}$在$\mathrm {V}$中是线性无关集合，而且$\mathrm {V}$中没有其他线性无关集合包含它作为真子集。
• $\mathrm {V}$中所有的向量都可以按唯一的方式表达为$\mathfrak {B}$中向量的线性组合。如果基是有序的，则在这个线性组合中的系数提供了这个向量关于这个基的坐标。

这换看起来还是不是人话，但是由于这里是最基础的部分，所以虽然看起来很繁琐，但是还是要严谨的写出来。

但是一般我们说的线性基是定义在 $GF(2)$ ，也就是所谓的二进制上的，一般用来解决异或问题，例如给你一堆二进制数，你可以从这些数中选出一个子集，这些子集的异或和构成一个线性空间，然后题目再在这个线性空间中询问一些信息。

所以上面那些不是人话的东西在二进制下可以写成

• 从 $\mathfrak {B}$ 中选出一个子集，求出它的异或和，这些异或和组成的集合就是 $\mathrm {V}$
• $\mathfrak {B}$ 的任意非空子集的异或和都不为 0，且 V 中找不到一个更大的符合条件的子集 $\mathfrak {B’}$ 满足这个条件且 $\mathfrak {B}$ 是 $\mathfrak {B’}$ 的真子集
• $\mathrm {V}$ 中的每一个数有一种唯一的从 $\mathfrak {B}$ 中选取一种子集的方式，满足这个子集异或和等于这个数

看着还是很抽象，但是好了很多，一般我们说把一个二进制数的集合求线性基，也就是说求这个集合所构成的线性空间的线性基。更直观的你可以理解为，把这个集合中能被其他数表示出来的数扔掉，留下一些不最基本的数，满足这个线性空间中每个数都能被这些数表示出来。

当然由于定义我们可以知道，线性基不仅可以定义在二进制下，也可以定义在别的线性空间中，例如三进制，不过我们今天写的是二进制的线性基操作。

三进制线性基的一道题：小W与屠龙游戏

基本操作

由于我们知道了线性基中的数线性无关，所以假设有两个数 $A$ ， $B$ 最高位相同，我们可以把 $A$ 变成 $A \oplus B$ ，从而使线性基中的每个数最高位都互不相同。我们可以使用一个数组 $val[]$ 来存储线性基中的元素，其中 $val[i]$ 表示最高位为 $i$ 的元素是多少（或是不存在）。

struct linear_basis
{
    ll val[maxn], tot; // val[i] 表示最高位为 i 的数, tot 表示线性基里数的数量
    const ll bit = 60;// 我们维护的线性基是几位的
    // operation...
}

插入

先假设这个数可以插入线性基，那么尝试找到这个这个新的数的最高位是什么，如果找着找着发现这个数直接变成 0 了，那么这个数和里面的数线性相关，没救了，否则这个数就可以插进线性基里面，最高位我们也顺势找到了。

bool add(ll a)
{
    per(i, bit - 1, 0)
    {
        if(!((a >> i) & 1)) continue;
        if(!val[i])
        {
            val[i] = a, ++ tot;
            return 1;
        }
        a ^= val[i];
    }
    return 0;
}

查询

查询某个数与这个线性空间里的数的异或的最大值

由于线性基的性质我们可以知道，线性空间里的每个数都可以有线性基里的一个子集的异或和唯一的表示出来，那么我们只要把这个数扔进基里贪心的看看每一位是否异或即可。

ll query_max(ll a)
{
    per(i, bit - 1, 0) chmax(a, a ^ val[i]);
    return a;
}

查询线性空间中第k大的值

我们可以把线性基中的每一个数看成控制了这个数的最高位（因为线性空间中的每个数是线性基的一个子集，选/不选 会使这个最高位的值为 0/1）。那么从高位往低位考虑，假设一个位被线性基控制了，那么无论更低的位怎么取，这个位取 1 总是大于这个位取 0。所以我们把这些被控制的位拿出来，那么最小的值显然是这些位都取 0，第二小的值显然是每个位都取 0，最低的那一位取 1……形式化的说，线性空间中第 $k$ 大的数，那么被控制的第 $i$ 大的位是否取 1 就看 $k - 1$ 二进制下第 $i$ 位是否为 1。

然后我们发现既然线性基都控制这些位了，那么我们也可以做线性空间中的数与某个数异或之后第 k 大的值了

ll query_kth(ll a, ll k)
{
    ll tmp = tot;
    per(i, bit - 1, 0)
    {
        if(!val[i]) continue;
        tmp --;
        if((k >> tmp) & 1) a = max(a, a ^ val[i]);
        else a = min(a, a ^ val[i]);
    }
    return a;
}

$*$ 查询一个集合内子集异或值的第 k 大

这个问题看起来和上个问题一样，但是有一些不同，首先这个集合的子集异或值构成了一个线性空间，但是线性基会比这个集合更小，因为存在一些数线性相关。其次就是我们要求的第 k 大，也就是有重复的数要算多遍，但是做法都一样。我们先找出这个集合的线性基，然后这个线性基构成的线性空间大小就是 $2^{tot}$ ，其中 $tot$ 为线性基大小。现在考虑每一个数出现的次数是多少。我们考虑那些不在线性基中，被我们抛弃了的数，这些数能被线性基中的数唯一表示，也就是说我们随意的选择这些基外的数，都可以通过选择线性基里的数进行调整，使得找出一个集合，他的异或和为0。于是显而易见的，每个数在这个集合中是 $2^{n-tot}$ 个子集的异或和，他会出现这么多次。其中 n 是这个集合的大小。

$*$ 查询一个数的排名

仔细看看上面找第 k 大的过程，发现其实就是找个二进制数一样，那么找一个数的排名也可以类似数位DP一样搞一搞就好了。

ll query_rnk(ll a)
{
    ll ret = 0, now = 0, tmp = tot;
    per(i, bit - 1, 0)
    {
        if(!val[i])
        {
            if((now >> i) < (a >> i)) return ret;
            if((now >> i) > (a >> i)) return ret + (1ll << tmp);
            continue;
        }
        tmp --;
        if((a >> i) & 1) now = max(now, now ^ val[i]);
        else ret += 1ll << tmp, now = min(now, now ^ val[i]);
    }
    if(now >= a) ++ ret;
    return ret;
}

进阶操作

合并

合并高级个🐘，就是把一个线性基中的每个数一个一个地插到另一个线性基中。

friend linear_basis operator + (linear_basis a, linear_basis b)
{
    per(i, bit - 1, 0) a.add(b.val[i]);
    return a;
}

求正交补

正交补是个什么东西？这个东西很抽象，大概就是我们把一个线性空间 $\mathrm{M}$ 里的每个向量 $\begin{bmatrix} a_1 ,a_2,a_3\dots a_n\end{bmatrix}$ 写出一个方程 $a_1x_1 +a_2x_3+\dots +a_nx_n=0$ ，然后所有方程构成一个方程组。我们把其中的一个解看做一个向量 $[x_1, x_2\dots x_n]$ ，然后所有解构成的所有向量形成的线性空间就是这个线性空间的正交补，记作 $\mathrm{M}^{\perp}$。

这个操作有性质：$(\mathrm{M}^{\perp})^{\perp} = \mathrm{M}$ ，和异或很像，做两次就回去了。

这个东西有什么用呢？只是为了求两个线性空间交的时候用的，别的性质👴⑧会。

linear_basis ort_cpl()
{
    linear_basis ret;
    per(i, bit - 1, 0) per(j, i - 1, 0) val[i] = min(val[i], val[i] ^ val[j]);
    rep(i, 0, bit - 1)
    {
        if(val[i]) continue;
        ll ans = 1ll << i;
        rep(j, i + 1, bit - 1) if(val[j] & (1ll << i)) ans += 1ll << j;
        ret.add(ans); 
    }
    return *this = ret;
}

求线性空间的交

据说有等式

$$A \cap B = (A^{\perp} \cup B^{\perp})^{\perp}$$

就是先正交补过去，并起来再正交补回来，🐘才知道为什么是对的。

friend linear_basis operator & (linear_basis a, linear_basis b)
{
    a.ort_cpl(), b.ort_cpl();
    // a.print(), b.print();
    a = a + b, a.ort_cpl();
    return a;
}

删除

上面我们所说的一切操作都是全局的，因为线性基不怎么好支持删除。所以遇到要删除的题，一般是离线的，按照并查集的套路搞一个线段树分治会好一点。如果硬要在线删除的话也不是没有办法，不过很麻烦，网上找找应该是有的。

区间询问

现在给你一个序列，每次询问你一个区间内的数异或构成的线性空间中最大值/第 k 大是多少。

假设我们询问的不是任意区间而是一个后缀的话，我们可以在线性基原有的信息上再记录一个时间戳，表示这一位是什么时候被加入的。插入的时候我们优先用时间戳更大的数更新时间戳小的数，后缀查询的话按照套路一个一个看过去，如果基里的一个元素存在且时间戳大于我们当前查询的左端点，那么他才是真实存在的，否则把这一位看做没有数就好了。

区间操作的话我们类似主席树一样，直接记录下每个前缀构成的线性基即可。