【概述】

线性基，是线性代数中的概念，在信息学竞赛中，前缀线性基是线性基的扩展，他们主要用于处理有关异或和的极值问题。

一组线性无关的向量即可作为一组基底，张起一个线性的向量空间，这个基底即称为线性基，利用线性基的基底进行线性运算，可表示向量空间内的所有向量，换句话说，所有向量都可以拆成基底的线性组合。

根据异或的原理，将一个数字拆成他的二进制形式，将二进制形式用向量来表示，由于一组线性无关的向量可以张起一个向量空间，因此可以考虑构造这样一组数字的二进制形式组成的线性基，在这个线性基中，通过基底的线性组合、异或运算，从而可以表达所有的异或结果。

简单来说，若一个数集 T 的值域范围为 ，那么 T 的线性基是 T 的一个子集 A={a1,a2,a3,...,an}，A 中元素相互异或而成的集合，等价于原数集 T 的元素相互异或形成异或集合

【线性基】

1.构造

线性基具有以下几个性质：

• 原数列中的任意一个数，均可由线性基中的一些数异或得到
• 线性基中的数的个数唯一，且在保证唯一性的前提下，数的个数是最少的
• 线性基的异或集合中，每个元素的异或方案唯一 ，且异或集合中不存在 0
• 线性基中元素互相异或，异或集合不变
• 线性基二进制最高位互不相同

1）插入

由于 xor 偶数具有抵消性，因此可利用这个性质对加入的向量进行修改。

对于每一个数来说，需要判断其是否能加入到线性基中，将新加入的数字 x 拆为二进制形式，从最高位向最低位扫描其为 1 的二进制位，扫描到第 i 位时，如果线性基向量组 d[i] 中不存在，即 d[i]=0 时，就令 d[i]=x，然后 break；反之，若线性基向量组 d[i] 中存在，即 d[i]=1 时，就令 x=x xor d[i]

这样在扫描完成后，新加入的数字 x，要么被添加进线性基，要么经过一系列操作后变成了 0，如果变成了 0，说明这个数字 x 对应的二进制向量不属于极大线性无关组。

LL d[60+5];//线性基 void add(LL x) {for(int i=60; i>=0; i--) {if(x&(1LL<<i)) {if(d[i])//插入失败，异或x^=d[i];else {//插入成功，保存后退出d[i]=x;break;}}} }

2）合并

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

LL d1[60+5],d2[60+5];//合并前的两个线性基 LL d[60+5];//合并后的线性基 void Union(){memcpy(d,d1,sizeof(d1));for(int i=0;i<=60;i++){if(d2[i])add(d2[i]);} }

2.查询

在线性基构造完毕后，即可对线性基进行查询。

1）最大值

当要查询最大值时，就从高位向低位扫描线性基，如果异或后使得结果变大，就异或进答案中。

LL d[60+5];//线性基 LL queryMax() {LL res=0;for(int i=60; i>=0; i--)if((res^d[i])>res)res^=d[i];return res; }

2）最小值

当要查询最小值时，最低位上的线性基即为答案。

LL d[60+5];//线性基 LL queryMin(){for(int i=0; i<=60; i++)if(d[i])return d[i];return 0; }

3）第 k 小值

由于线性基二进制最高位互不相同，因此要将线性基改造为每一位相互独立。

从最高位向最低位枚举，如果 i<j，那么 d[j] 的第 i 位是 1，就将 a[j] 异或上 a[i]，经过一系列操作后，对于二进制的某一位 i，只有 a[i] 这一位是 1，其余的都是 0

这样在查询的时候，将 k 进行二进制拆分，对于为 1 的位，就异或上对应的线性基，最终得到的就是第 k 小的值

注：如果要求第 k 大的值，也就是求第 n-k+1 小的值，将 queryKth() 的参数 k 换为 n-k+1 即可

LL d[60+5];//线性基 LL p[60+5];//改造后的线性基 int cnt; void rebuild() {//改造线性基for(int i=60; i>=0; i--)for(int j=i-1; j>=0; j--)if(d[i]&(1LL<<j))d[i]^=d[j];for(int i=0; i<=60; i++)if(d[i])p[cnt++]=d[i]; } LL queryKth(LL k){//查询第k小的值，若要查k大，将k换为n-k+1即可int res=0;if(k>=(1LL<<cnt))return -1;for(int i=60; i>=0; i--)if(k&(1LL<<i))res^=p[i];return res; }

【前缀线性基】

线性基用于处理整个区间异或的极值问题，前缀线性基用来维护整个区间中的一段区间异或的极值问题。

1.构造

前缀线性基建立在线性基的基础上，其是对于 i 都建立一个 1~i  数组成的线性基。

假设有 4 个数 1、2、3、4，那么就建立 4 个基底，分别为：

• 第一基底：1
• 第二基底：1、2
• 第三基底：1、2、3
• 第四基底：1、2、3、4

在构造 i 个基底时，先将前 i-1 个 基复制过来，然后再加上第 i 个数，来构造一个新的基底。

如果对于基底的某个位置上的数有能更新的数，就进行替换，以保证对于某个右端点 R 能尽可能的用靠近 R 的数作为基，也就保证了所有 [L,R] 中的数都尽可能的参与构造这个数。

例如：对于第五个基的第 3 个位置，如果第 4 个数和第 2 个数都能放在这个位置，那么就放第 4 个数，因为查询区间 [3,5] 时能用 3、4、5 构造这个数，包含了 4；查询区间 [2,5] 时，能用 2、3、4、5 构造这个数

也就是说对于 [2,5] 来说，第 2 个数还是第 4 个数都可以使用，但是 [3,5] 来说，只能使用第 4 个数，因此当第 4 个数和第 2 个数都能放在第 3 个位置时，优先用第 4 个数

void add(int x) { //向线性基中添加xnum++;for(int i=0; i<32; i++) { //复制前num-1个线性基d[num][i]=d[num-1][i];pos[num][i]=pos[num-1][i];}int P=num;for(int i=31; i>=0; i--) {if((x>>i)&1) {if(d[num][i]) { //插入失败if(pos[num][i]<P) { //交换位置swap(pos[num][i], P);swap(d[num][i],x);}x^=d[num][i];//异或} else { //插入成功d[num][i]=x;pos[num][i]=P;break;}}} }

2.查询

在查询 [L,R] 区间时，就找到第 R 个基，然后用 pos[i] 来记录第 i 个位置是哪个数，如果 pos<l，那么就说明不是区间 [L,R] 的基

1）最大值

int queryMax(int l,int r) { //查询[l,r]中的最大值int res=0;for (int i=31; i>=0; i--) {if(pos[r][i]<l)continue;if ((res^d[r][i])>res)res^=d[r][i];}return res; }

2）最小值

int queryMin(int l,int r) {//查询[l,r]中的最小值for(int i=0; i<=60; i++) {if(pos[r][i]<l)continue;if(d[r][i])return d[r][i];}return 0; }

【模版】

1.线性基

struct LinearBasis {int num;//线性基中元素个数LL d[60+5];//线性基LL p[60+5];//查询第k小时的改造的线性基int cnt;//改造线性基用LinearBasis() {memset(d,0,sizeof(d));memset(p,0,sizeof(p));num=0;cnt=0;}bool add(LL x){for(int i=60; i>=0; i--) {if(x&(1LL<<i)) {if(d[i])//插入失败，异或x^=d[i];else {//插入成功，保存后退出num++;//统计线性基中元素个数d[i]=x;break;}}}return x>0;//x>0插入成功}LL queryMax() {//查询最大值LL res=0;for(int i=60; i>=0; i--)if((res^d[i])>res)res^=d[i];return res;}LL queryMin() {//查询最小值for(int i=0; i<=60; i++)if(d[i])return d[i];return 0;}void rebuild() {//改造线性基for(int i=60; i>=0; i--)for(int j=i-1; j>=0; j--)if(d[i]&(1LL<<j))d[i]^=d[j];for(int i=0; i<=60; i++)if(d[i])p[cnt++]=d[i];}LL queryKth(LL k) {//查询第k小的值，若要查k大，将k换为n-k+1即可int res=0;if (k>=(1LL<<cnt))return -1;for (int i=60; i>=0; i--)if (k&(1LL<<i))res^=p[i];return res;} }; LinearBasis Union(const LinearBasis &rhs1,const LinearBasis &rhs2) {LinearBasis res=rhs1;for(int i=60; i>=0; i--)if(rhs2.d[i])res.add(rhs1.d[i]);return res; }

2.前缀线性基 

struct PrefixLinearBasis{int d[N][32];//前缀线性基int pos[N][32];//最后一个修改i这个位置的数int num;//线性基中元素个数PrefixLinearBasis(){memset(d,0,sizeof(d));memset(pos,0,sizeof(pos));num=0;}void clear(){memset(d,0,sizeof(d));memset(pos,0,sizeof(pos));num=0;}void add(int x){//向线性基中添加xnum++;for(int i=0; i<32; i++){//复制前num-1个线性基d[num][i]=d[num-1][i];pos[num][i]=pos[num-1][i];}int P=num;for(int i=31; i>=0; i--){if((x>>i)&1){if(d[num][i]){//插入失败if(pos[num][i]<P){//交换位置swap(pos[num][i], P);swap(d[num][i],x);}x^=d[num][i];//异或}else{//插入成功d[num][i]=x;pos[num][i]=P;break;}}}}int queryMax(int l,int r){//查询[l,r]中的最大值int res=0;for (int i=31; i>=0; i--){if(pos[r][i]<l) continue;if ((res^d[r][i])>res) res^=d[r][i];}return res;}int queryMin(int l,int r) {//查询[l,r]中的最小值for(int i=0; i<=60; i++){if(pos[r][i]<l)continue;if(d[r][i])return d[r][i];}return 0;} }PLB;

【例题】

• 彩灯（洛谷-P3857）(线性基中元素个数)：点击这里
• 元素（HYSBZ-2460）(添加线性基+贪心)：点击这里
  同题：元素（洛谷-P4570）：点击这里
• 幸运数字（洛谷-P3292）(最大异或和+LCA)：点击这里
• Operation（HDU-6579）(前缀线性基)：点击这里
• Ivan and Burgers（CF-1100F）(前缀线性基)：点击这里

总结

以上是生活随笔为你收集整理的线性代数 —— 线性基与前缀线性基的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。