线性基学习笔记

线性基是一种经常用于解决集合异或问题的数据结构。其实与其说它是数据结构,说它是一种巧妙的构造算法更恰当。

定义

非负整数集合 SS 的线性基 AA 满足一些美妙的性质:

  1. AA 是一个集合;
  2. SS 能异或出来的所有非负整数,AA 都能异或出来,但 AA 的所有真子集都不能完全异或出来,也就是说 AA极小的
  3. SS 能异或出来的所有非负整数集合为 TT,那么 TT 中的每一个元素都仅可以被 AA 中的某个特定子集 BB 异或出来

简单来说,线性基就是一个关于非负整数集合 SS 的特殊的集合,它很小但又可以异或出 SS 能异或出来的所有值。

构造

考虑线性基的构造,可以构造一种特殊的线性基使得:

  1. AA 是一个有序序列;

  2. 对于每个 ii

    1. 要么 AA有且仅有 AiA_i 的二进制第 ii 位为 11,且 AiA_i二进制最高的为 11 的位是第 ii

    2. 要么 Ai=0A_i=0只有所有满足 j>ij>iAjA_j 二进制的第 ii 位为可能为 11

  3. A|A| 最大为 logV\log V,其中 VV 是值域;

具体方法是,先让 A={0,0,,0}A=\{0,0,\dots,0\},然后不断的把 SS 中的元素插入 AA。一次插入的流程如下:(设插入的非负整数为 xx

从高位到低位枚举,假设枚举到第 ii 位,显然xx 的二进制中第 ii 位为 00xx 不可能插入此处,直接跳过即可。否则:

  • Ai=0A_i\not=0,那么此时 xx 肯定无法插入此处。由于要保证性质 2.1 中关于最高位的性质,所以需要删掉 xx 的第 ii 位。又由于要满足线性基的性质 2,所以我们不能直接让 xx 减去 2i2^i,而是应该xxxorAix\to x\operatorname{xor} A_i,因为这样可以保证最终插入 AAxx 异或上 AiA_i 还可以表示原来插入的 xx,这样也不会让 AA 中的元素能异或出其它的值或让 AA 不再是极小的

  • Ai=0A_i=0,那么:

    1. xx 异或上所有满足 j<ij<ixx 的二进制中第 jj 位为 11AjA_j,这样做是为了保证性质 2.1 中有且仅有 AjA_j 的二进制第 jj 位可能为 11 的性质,所以要通过异或操作把 xx(未来的 AiA_i) 的这些位删掉,不直接减去 2j2^j 的原因同上。
    2. AixA_i\to x
    3. 所有满足 j>ij>iAjA_j 都异或上 AiA_i,这样做同样是为了保证性质 2.1 中有且仅有 AjA_j 的二进制第 jj 位可能为 11 的性质
    4. 结束插入;

执行完插入流程后,若 x=0x\not=0 那么插入就成功了,否则就表明当前的线性基中的元素已经能异或出 xx,无需插入。但是若 x=0x=0 就表明插入失败,即线性基已经能异或出 xx 了。

插入代码如下:

long long a[65];
bool has0;

inline void ins(long long x)
{
	for(int i=60;i>=0&&x>0;i--) // 注意一定要倒序枚举!因为要消掉 x 的二进制高位的 1,并且需要对 x 的二进制的低位造成影响
	{
		if((x>>i)&1) // x 的二进制这一位为 1
		{
			if(a[i]==0) // 可以插入
			{
				for(int j=i-1;j>=0;j--) if((x>>j)&1) x^=a[j]; // 这个循环的顺序不重要
				// 因为所有满足 j<i 的不为 0 的 A[j] 都不会影响到其它不为 0 的 A[j]
				a[i]=x; // 插入
				for(int j=i+1;j<=60;j++) if((a[j]>>i)&1) a[j]^=a[i]; // 把所有满足 j>i 且 A[j] 的二进制第 i 位为一的 A[j] 的二进制第 i 位消去
				break;  // 记得结束插入过程
			}
			else x^=a[i]; // 不能插入,消去这一位
		}
	}
	if(x==0) has0=true;
}

查询

把非负整数集合 SS 的元素都插入线性基后,线性基能支持几种关于异或的查询。

SS 有多少个不同的子集异或和为 xx

首先检查是否能异或出 xx,若可以,那么 xx 异或上线性基外的任意几个数得到的 xx' 都可以被线性基异或出来,所以答案为 2nsiz2^{n-siz},其中 siz=[Ai=0]siz=\sum [A_i\not=0]

SS 的子集的最大异或和

由于构造出来的线性基满足有且仅有 AiA_i 的二进制中第 ii 位为 11,所以 AiA_i 中参与异或运算的元素越多结果就越大,让所有 AiA_i 异或起来的结果 xsumxsum 肯定是 AiA_i 的所有子序列的异或和中最大的。又由于线性基可以异或出 SS 能异或出的所有值,所以 xsumxsum 就是 SS 的子集的最大异或和。

代码如下:

inline long long quemx()
{
	long long res=0;
	for(int i=0;i<=60;i++) res^=a[i];
	return res;
}

SS 的子集的最小异或和

由于 AiA_i 中参与异或运算的元素越多结果就越大,所以最优的情况显然是只让 AA 中的一个元素参与异或运算,所以返回 AA 中的最小值即可。不过要特判 00 的情况。

代码如下:

inline long long quemn()
{
	if(has0) return 0;
	long long mn=2e18;
	for(int i=0;i<=60;i++) mn=min(mn,a[i]);
	return mn;
}

SS 的子集的第 kk 小异或和

首先线性基中的元素是异或不出 00 的,所以SS 可以异或出 00,即 has0=truehas0=true,那么就需要让 kk1k\to k-1

由于 AA 中只有不为 00 的元素才对异或和有贡献,所以不妨用一个数组 BB 依次记录下 AA 中不为 00 的值

显然,由于线性基可以异或出 SS 能异或出的所有值,所以 2B12^{|B|}-1BB 的非空子序列都可以异或出互不相同的值,所以k>2B1k>2^{|B|}-1 就无解

由于构造出来的线性基满足有且仅有 AiA_i 的二进制中第 ii 位为 11,所以对于任意一个 0iB0\le i\le |B| 的非负整数 ii任意一个非负整数异或上 BiB_i 得到的结果都它比依次异或上 B1,B2,B3,Bi1B_1,B_2,B_3,\dots B_{i-1},这和二进制很像。

那么解法就很明显了,把所有满足 kk 的二进制中第 ii 位为 11BiB_i 异或起来,我们就能得到 SS 的子集的第 kk 小异或和。

代码如下:

long long b[65];

inline long long kth(long long k)
{
	if(has0) k--;
	int len=-1;
	for(int i=0;i<=60;i++) if(a[i]!=0) b[++len]=a[i];
	long long ans=0;
	for(int i=0;i<=len;i++) if((k>>i)&1) ans^=b[i],k^=1ll<<i;
	return k>0?-1:ans;
}

额外的操作

线性基还支持一些其它的操作。

合并

两个线性基合并,只需要暴力把一个线性基中的所有元素插入到另一个线性基中即可。容易证明插入完成的线性基还是满足所有性质的。

可持久化

由于线性基数组 AA 很短,所以可以用二维数组来实现可持久化,时间和空间复杂度都是 O(qlogV)O(q\log V) 的。其中 qq 为操作次数,VV 则表示值域大小。


upd:2025.06.21

带删除

离线可以直接抠背包(线段树分治),做到 O(nlognlogw)O(n\log n\log w),或者说 O(nlognmω)O(n\log n\frac{m}{\omega}),其中 mm 是维数。

或者可以给每个基打时间戳,插入的时候维护一下每个基的最晚出现时间(适用于双指针)。

而用一堆分讨可以做到在线,单次 O(logw)O(\log w) 或者 O(m2ω)O(\frac{m^2}{\omega})(和插入同阶)。

具体的,每个元素插入的时候额外维护一个 idiid_i 表示它最后由那些元素组成(即最后变成某个基或者变成 00 时具体异或上了原来插入的哪些元素)。

那么分讨一下,假设删除的是 xx

  • 如果删除的元素不在线性基中,直接删除即可;
  • 否则要消去 xx 带来的影响:
    • 若存在一个不在线性基中的元素(插入时被消成了 00),满足其 idid 包含 xx,那么 xx 将会在这个地方复活,处理一下;
    • 否则秩将会减一,此时:
      • 找到线性基中最小的,idid 包含 xx 的基 zz
      • 将所有 idid 包含 xx 的基全部异或上 zzzz 也要异或自己,相当于变成了 00);

这样做显然是对的。