ID: 555

客观题

难度: 7

上传者:

boya

标签>

教程

线性空间

线性空间是一个关于以下两个运算封闭的向量集合：

向量加法 $a+b$ , 其中 $a,b$ 均为向量。
标量乘法 $k\cdot a$ , 也称数乘运算，其中 $a$ 是向量， $k$ 是常量（标量）。

给定若干个向量 $a_1,a_2,\dots , a_k$ ,若向量 $b$ 能由 $a_1,a_2,\dots ,a_k$ 经过向量加法和标量乘法运算得出，则称向量 $b$ 能被向量 $a_1,a_2,\dots,a_k$ 表出。显然， $a_1,a_2,\dots,a_k$ 能表出的所有向量构成一个线性空间， $a_1,a_2,\dots,a_k$ 被称为这个线性空间的生成子集。

任意选出线性空间中的若干个向量，如果其中存在一个向量能被其他向量表示，则称这些向量线性相关，否则称这些向量线性无关。

线性无关的生成子集被称为线性空间的基底，简称基。 基的另一种定义是线性空间的极大线性无关子集。一个线性空间的所有基所包含的向量个数都相等，这个数被称为线性空间的维数。

例如向量 $a=(1,0),b=(0,1),c=(1,1)$ , 其中 $c=a+b$ , 我们称向量 $a,b,c$ 线性相关。但是向量 $a=(1,0),b=(0,1)$ 线性无关，它们也是线性空间的基底。当然 $a=(1,0), c=(1,1)$ 也是一组基底。二维线性空间基底数量是 $2$ ，也就是二维线性空间的维数是 $2$

对于线性空间的一组基，基内任意一个向量元素不能被基内其他向量表示出来，线性无关。

对于一个 $n$ 行 $m$ 列的矩阵，我们可以把它的每一行看作一个长度为 $m$ 的向量，称为“行向量”。矩阵的 $n$ 个行向量能够表出的所有向量构成一个线性空间，这个线性空间的维数被称为矩阵的“行秩”。类似地，我们可以定义列向量和列秩。实际上，矩阵的行秩一定等于列秩，它们都被称为矩阵的秩。

把这个 $n*m$ 的矩阵看作“系数矩阵”进行高斯消元（增广矩阵的最后一列全看作零），得到一个简化阶梯形矩阵。简化阶梯形矩阵的所有非零行向量线性无关。因为初等行变换就是行向量之间进行的向量加法与标量乘法运算，所以高斯消元不改变矩阵的行向量表出的线性空间。于是，简化阶梯形矩阵的所有非零行向量就是该线性空间的一个基，非零行向量的个数就是矩阵的秩。

例 [JLOI2015] 装备购买

【题意简化】游戏中有 $n(\le 500)$ 件装备, 每件装备有 $m(\le 500)$ 个属性，用向量 $z_i=(a_{i1},a_{i2},\dots ,a_{i,m})$ 表示，需要花费 $c_i$ 。如果一件装备的属性能被其他装备用线性组合出来，那么这件装备肯定不购买。买最多装备的情况下，请问花费最小的钱数是多少？

【分析】最多装备的数量就是线性无关的向量个数，也就是矩阵的秩。本题需要求花最少的钱，在高斯消元过程中可以使用贪心策略，对于每个主元 $x_{col}$ ,前 $col-1$ 列为 $0$ 、第 $col$ 列不为 $0$ 的行向量中，选择价格最低的一个，消去其他行中第 $col$ 列的值。

“高斯消元+贪心”

异或空间线性基

线性空间的概念可以进一步推广，不仅限于向量、向量加法和标量乘法。例如“异或空间”就是一个很常见的形式。异或空间是一个关于异或运算封闭的非负整数集合。

可以在异或空间中用类似的方法定义“表出”“线性无关”“基底”等。

若整数 $b$ 能由整数 $a_1,a_2,\dots,a_k$ 经异或运算得出，则称 $b$ 能被 $a_1,a_2,\dots,a_k$ 表出。 $a_1,a_2,\dots,a_k$ 能表出的所有整数构成一个异或空间， $a_1,a_2,\dots,a_k$ 被称为这个异或空间的生成子集。

任意选出异或空间中的若干个整数，如果其中存在一个整数能被其他整数表出，则称这些整数线性相关，否则称这些整数线性无关。异或空间的基就是异或空间中一个线性无关的生成子集，或者定义为异或空间的极大线性无关子集。

高斯消元法求异或空间基

给定 $n$ 个 $0\sim 2^B-1$ 之间的整数 $a_1,a_2,\dots , a_n$ , 如何求出这 $n$ 个整数表出的异或空间的基？

我们可以把它们看作 $B$ 位二进制数，写成一个 $n$ 行 $m$ 列的 $01$ 矩阵，矩阵中第 $i$ 行从左到右依次是 $a_i$ 的第 $m-1,m-2,\dots,0$ 位（二进制的最低位称为第 $0$ 位）。把矩阵作为系数矩阵，用高斯消元求解异或方程组的方法，将其转化为简化阶梯形矩阵。简化阶梯形矩阵的每一行也是一个整数，所有非零整数一起构成异或空间的基。

以异或线性基为例，我们可以根据给定的一组整数序列 $\{x_1,\dots,x_m\}$ 构造出一组异或线性基 $base[]=\{b_0,\dots,b_{B-1}\}$ ，这组基有如下性质：

$base[]$ 中任意非空子集的异或和不为 $0$ ;
对 $X$ 中的任意元素 $x$ ，都可在 $base[]$ 中取出若干元素使其异或和为 $x$ ;
对任意满足上两条的集合 $base[]'$ ，其元素个数不会小于 $base[]$ 的元素个数。

利用异或线性基实现

1.判断一个数能否表示成某数集子集的异或和；
2.求一个数表示成某数集子集异或和的方案数；
3.求某数集子集的最大/最小/第 $k$ 大/第 $𝑘$ 小异或和；
4.求一个数在某数集子集异或和中的排名。

对于 $n$ 个数的集合求线性基，本质在异或线性空间中寻找“极大线性无关无关组” ，“高斯消元法”肯定正确，并且在维护第 $k$ 小避免不了，但是对于一般情况我们可以贪心构造线性基，时间复杂度更低，需要变换成“简化阶梯形”再对线性基进行“消元”处理，时间复杂度低，代码也简洁易懂。

接下来我们以贪心插入法讲解线性基。

【线性基】

对于 $n$ 个数的集合 , 线性基个数不会超过最大数的二进制位数，以 unsigned long long 范围为例，线性基集合数量不会超过 $64$ 个，可以定义 unsigned long long base[64]作为线性基。 $base_i$ 表示最高位的 $1$ 在第 $i$ 位的基向量

当插入一个数 x , 从高位往低位扫描 x 二进制下的第 i 位，当 x 第 i 位不为 $0$ , 检查 base[i]:

如果 base[i] 为 0 ,则令 base[i]=x , 结束返回。（插入成功）
如果 base[i] 不为 0 ，则令 x=x^base[i] , 继续向低位插入。

1.插入

ull base[64];
void insert(ull x)
{
    for(int i=63;i>=0;i--)
        if((x>>i)&1)
        {
            if(base[i])x^=base[i];  //将x 第 i 位异或为0 往低位线性基插入
            else {
                base[i]=x;   //插入成功
                return;
            }
        }
}

注： ull 指 unsigned long long

单次插入时间复杂度就是 $O(B)$ , $B$ 是二进制位数，也是线性基元素个数,一般取 64 或 32 。

2. 线性基合并

当两个线性基需要合并时，直接将一个线性基暴力的插入另一个线性基即可。

struct XXJ{
    ull base[64];
    XXJ()  //构造函数
    {
        memset(base,0,sizeof(base));
    }
};
XXJ merge(XXJ u,XXJ v)  //线性基合并
{
    for(int i=63;i>=0;i--)
        if(v.base[i])u.insert(v.base[i]);
    return u;
}

单次合并时间复杂度就是 $O(B^2)$ 。线性基基本合并功能，那么就可以利用线段树等数据结构维护线性基了，只是有的时候时间复杂度太大，往往 $O(n\log{n}B^2)$ 。

3. 查询

对于贪心插入法构造的线性基，需要查询最大值，由于贪心法构造的线性基，还不是简化阶梯型，所有基异或后可能会更小，需要异或的时候保留最大。如果是高斯消元法建立的线性基，已经是简化阶梯型了，那么所有基向量异或和就是答案。

查询最大值

ull query_max()
{
    ull  ans=0;
    for(int i=63;i>=0;i--)
        ans=max(ans,ans^base[i]);
    cout<<ans;
}

对于查询最小值的情况，如果非零基个数大于等于原集合数 $n$ ，那么最小的非零 $base_i$ 就是答案，否则就是 0.

查询第 $k$ 小

采用贪心法构造的线性基，需要提前进行“简化阶梯型”消元处理，消元之后从小到大预处理，处理后的基取或者不取，就能拼凑出第 $k$ 小。消元预处理之后，从小到大取出所有非零基向量，令 b[0]...b[cnt-1] 表示预处理之后的非零基向量。

对应其任意子集，能够构成第 $1\sim 2^{cnt}-1$ 小的数，当 $k>=2^{cnt}$ 时，无法构成。例如子集 00101 表示取出 $b[2],b[0]$ , 那么一定可以构成第 $5$ 小的数。

要注意特殊情况，当基的个数 $cnt<n$ 时，原集合异或后能够得到 $0$ ，最小的值就是 $0$ ，而我们讨论的都是非零异或和，需要 k--。

核心参考代码：

ull base[64],b[64];
void prework()
{
    //阶梯型处理，相当于高斯消元
    for(int i=50;i>=0;i--)
        for(int j=i-1;j>=0;j--)
            if((base[i]>>j)&1)base[i]^=base[j];
    
    //从小到大取出非零基 b[0]...b[cnt-1]
    cnt=0;
    for(int i=0;i<=50;i++)
        if(base[i])b[cnt++]=base[i];
}
ll get_kth(ll k)
{
    if(cnt<n)k--;  //线性基能构成 0 
    if(k>=(1ll<<cnt))return -1;  //只能构成第 1- （2^cnt-1）小 这些值
    ll res=0;
    for(int i=0;i<=50;i++)
        if((k>>i)&1)
            res^=b[i];
    return res;
}

例2. LOJ114 k 大异或和

【题意简化】给定 $n(\le 10^5)$ 个数 ( $\le 2^{50}$ ) 组成的可重集，在所有非空子集不同的异或和中，寻找第 $k$ 小。

同类型题目：HDU3949 XOR

【分析】利用贪心插入建立的线性基，需要进行“阶梯化”消元预处理，预处理之后，从小到大取出所有非零基 $d_i(i=0\sim cnt-1)$ 。基取或者不取，总共可以构成 $2^{cnt}-1$ 个不同的非零数，接下来拼凑出第 $k$ 小。以 $k=3=(0011)_2$ 为例，第 1/2/3 小的数是 $d_0,d_1,d_0 \oplus d_1$ 。如果 ((k>>i)&1)==1 ,第 $i$ 小的基 $d_i$ 应该取，取出所有的基，求其异或和就是答案。

要注意特殊情况，如果 n>cnt 子集异或和能得到 $0$ , 而上面算法，求得是非零，那么对 k-- ，参考代码：

参考代码：点击

【前缀线性基】

前缀线性基是一种用于高效处理序列子区间异或最值查询的强大数据结构，它巧妙地将线性基与“前缀”思想结合，实现了对大量区间查询的快速响应。

【问题引入】

给定一个长度为 $n$ 的序列 $a[1..n]$ ，有 $q$ 次询问，每次询问要求计算子区间 $[L, R]$ 内所有子序列（或子集）的最大异或和。

【分析】暴力构造每个区间线性基，时间复杂度无法接受。如果使用 st 表或者线段树，合并依次时间复杂度就是 $O(B^2)$ ，其中 $B$ 是二进制位数（线性基个数），那么时间复杂度就是 $O(n\log{n}*B^2)$ , 时间复杂度还是太高了。

前缀线性基，在维护基的同时，额外维护一个信息：这个基向量是由原序列中哪个位置（下标）的数产生的。

具体说，就是我们为序列的每一个前缀 [1...i] 都维护一个线性基 base[i][0...B-1] 和对应的位置组 pos[i][0...B-1] 。 base[i] 表示考虑前 i 个数时，最高位的 1 在第 j 位的基向量；pos[i][j] 则表示这个基向量最后一次被更新时所使用的数的下标。

1.构建过程

构建过程是一个增量插入过程。假设已经构建好了前 i-1 个前缀线性基 base[i-1][] 和 pos[i-1][] ,现在要插入第 i 个数 x=a[i] , 插入时间戳 tim=i

首先复制 base[i-1][] 和 pos[i-1][] 到 base[i][] 和 pos[i-1][] ;

接下来从高位到低位依次扫描 x 二进制下的第 j 位，如果不为 0 , 则检查 base[i][j]:

1. 如果 base[i][j] 为 0 ，则令 base[i][j]=x,pos[i][j]=tim ,然后结束。
1. 如果 base[i][j] 不为 0 ，则比较 pos[i][j] 与当前 $x$ 的插入时间戳 tim .
- 如果 pos[i][j]<tim （之前基向量早一些），我们希望用更新、更靠右的数作为基向量 ，这样后续区间查询时，这个基向量更有可能落在 $[L,R]$ 内。因此，操作变为：交换 x 与 base[i][j] ，交换 tim 与 pos[i][j](同时交换它们的来源下标)。然后继续用新的 x（即原来的基向量）向低位尝试插入。

这个交换操作是前缀线性基算法的精髓。它保证了对于每个固定的右端点 R，其对应的线性基 base[R][] 中，每一位上的基向量都尽可能来自靠右的位置。这样，在查询时，我们就能通过比较 pos[R][j] 与查询左端点 L 的关系，快速判断这个基向量是否在区间 [L, R] 内。

构建过程的伪代码逻辑如下:

初始化 base[] 和 pos[] 全为 0。
for i from 1 to n:
    将 base[i-1][] 和 pos[i-1][] 复制到 base[i][] 和 pos[i][]。
    令 x = a[i], tim = i。
    for j from 高位到低位：
        if (val 的第 j 位是 1):
            if (base[i][j] == 0):
                base[i][j] = x, pos[i][j] = tim; break;
            else:
                if (pos[i][j] < p):
                    交换(base[i][j], x);
                    交换(pos[i][j], tim);
                x = x ^ base[i][j];

2.查询

当我们需要回答一个查询 [L, R] 时，我们直接使用为前缀 R 构建好的线性基 base[R][] 和位置信息 pos[R][]。

查询算法与标准线性基求最大异或和几乎一样，只是多了一个过滤条件：遍历所有基向量 base[R][j] ，只有当 pos[R][j] >= L 时，我们才考虑使用 base[R][j] 这个基向量。因为 pos[R][j] 记录了该基向量在序列中的下标，只有当这个下标大于等于查询区间的左端点 L 时，这个数才确实存在于区间 [L, R] 中，可以被用于异或。

查询伪代码：

ans = 0
for j from [0...B-1]：
    if (pos[R][j] >= L) and ((ans ^ base[R][j]) > ans):
        ans = ans ^ base[R][j]
return ans

正确性核心点在于：交换操作保证了对于任意一个二进制位 j ，在 base[R][j] 中存储的是前 R 个数中，能提供该位、且下标最大的那个数所构成的基向量形式。当查询左端点 L 小于等于这个最大下标时，这个基向量就是可用的；否则，说明在区间 [L, R] 内没有任何数能提供这个最高位，因此这一位在最终答案中无法置为 1。

3.复杂度与特点

预处理时间复杂度： $O(n * B)$ ，其中 $B$ 是数的二进制位数（通常为 32 或 64 ）。
单次查询时间复杂度： $O(B)$ 。
空间复杂度： $O(n * B)$ 。
优点：查询极快，非常适合处理大量静态区间查询。
缺点：不支持修改（因为是静态前缀和结构），且空间消耗较大。对于可修改或动态的问题，通常需要借助线段树维护线性基合并等功能。

例1.CF1100F - Ivan and Burgers

【题意简化】给定一个长度为 $n(\le 5 \times 10^5)$ 整数序列 $c_i$ , $q(5\times10^5)$ 次询问区间 $[l,r]$ 内异或和的最大值。

【分析】前缀线性基模板题

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+10;
int n,q,a[N];
int base[N][21],pos[N][21];  //前缀线性基
void insert(int x,int i)
{
    for(int j=20;j>=0;j--)
        base[i][j]=base[i-1][j],pos[i][j]=pos[i-1][j];

    int tim=i;
    for(int j=20;j>=0;j--)
        if((x>>j)&1)
        {
            if(base[i][j])
            {
                if(pos[i][j]<tim)
                {
                    swap(x,base[i][j]);
                    swap(tim,pos[i][j]);
                }
                x^=base[i][j];
            }
            else{
                base[i][j]=x;
                pos[i][j]=tim;
                return;
            }
        }
}
int q_max(int L,int R)
{
    int ans=0;
    for(int j=20;j>=0;j--)
        if(pos[R][j]>=L)
        ans=max(ans,ans^base[R][j]);
    return ans;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];

        insert(a[i],i);  //创建前缀线性基
    }
    cin>>q;
    while(q--)
    {
        int l,r;
        cin>>l>>r;
        cout<<q_max(l,r)<<"\n";
    }    
    
    return 0;
}

例2.P3292 [SCOI2016] 幸运数字

【题意简化】给定 $n$ 个节点的树，每个节点有一个权值 $G_i$ ， $q$ 次询问点 $x$ 到点 $y$ 路径上点权子集最大异或和。(早年题目 $n$ 比较小, $n\le 2e4 ,G_i \le 2^{60}, q \le 2e5$ )

【分析】本题是前缀线性基搬到树上的模板题。

先提供一种复杂度较大的倍增做法，可以定义 $g[x][i]$ 表示点 $x$ 到 $x$ 的 $2^i$ 级祖先路径上的线性基，那么利用线性基合并可以得到，g[x][i]=merge(g[x][i-1],g[fa[x][i-1]][i-1]) ，预处理时间复杂度是 $O(n\log{n} B^2)$ . 接下来倍增计算 $x$ 到 $lca$ 的线性基，合并 $y$ 到 $lca$ 线性基，从而得到路径 $x$ 到 $y$ 的线性基，时间复杂度是 $O(n\log{n}B^2)$ ，由于早年题目 $n$ 较小可以卡过去，但这不是最优做法。

可以利用前缀线性基，计算每个节点到树根的前缀线性基，当前节点 $now$ 从其父亲节点线性基得到，那么对于路径 $x$ 到 $y$ 的路径上的线性基，就变成区间 $[lca,x]$ 与 $[lca,y]$ 线性基的合并。注意为了保证节点单调性，应该使用 dfs 序创建前缀线性基。

参考代码：点击

线性基具有可并性，那么就可以利用很多数据结构维护，也可以与图结合，更多例题应用，请点击线性基应用

学习完毕

{{ select(1) }}

#edu2075. 【教程】线性空间与线性基

【教程】线性空间与线性基

线性空间

例 [JLOI2015] 装备购买

异或空间线性基

高斯消元法求异或空间基

利用异或线性基实现

【线性基】

1.插入

2. 线性基合并

3. 查询

查询最大值

查询第 $k$ 小

例1. P3812【模板】线性基

例2. LOJ114 k 大异或和

【前缀线性基】

【问题引入】

1.构建过程

2.查询

3.复杂度与特点

例1.CF1100F - Ivan and Burgers

例2.P3292 [SCOI2016] 幸运数字

学习完毕

状态

开发

支持

#edu2075. 【教程】线性空间与线性基

【教程】线性空间与线性基

线性空间

例 [JLOI2015] 装备购买

异或空间线性基

高斯消元法求异或空间基

利用异或线性基实现

【线性基】

1.插入

2. 线性基合并

3. 查询

查询最大值

查询第 kkk 小

例1. P3812【模板】线性基

例2. LOJ114 k 大异或和

【前缀线性基】

【问题引入】

1.构建过程

2.查询

3.复杂度与特点

例1.CF1100F - Ivan and Burgers

例2.P3292 [SCOI2016] 幸运数字

学习完毕

状态

开发

支持

还没有账户？

登录

查询第 $k$ 小