线性基学习笔记

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

定义

非负整数集合 $S$ 的线性基 $A$ 满足一些美妙的性质：

1. $A$ 是一个集合；
2. $S$ 能异或出来的所有非负整数，$A$ 都能异或出来，但 $A$ 的所有真子集都不能完全异或出来，也就是说 $A$ 是极小的；
3. 记 $S$ 能异或出来的所有非负整数集合为 $T$，那么 $T$ 中的每一个元素都仅可以被 $A$ 中的某个特定子集 $B$ 异或出来；

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

构造

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

1. $A$ 是一个有序序列；

2. 对于每个 $i$：

   1. 要么 $A$ 中有且仅有 $A_i$ 的二进制第 $i$ 位为 $1$，且 $A_i$ 的二进制最高的为 $1$ 的位是第 $i$ 位；

   2. 要么 $A_i=0$ 且只有所有满足 $j>i$ 的 $A_j$ 二进制的第 $i$ 位为可能为 $1$；

3. $|A|$ 最大为 $\log V$，其中 $V$ 是值域；

具体方法是，先让 $A=\{0,0,\dots,0\}$，然后不断的把 $S$ 中的元素插入 $A$。一次插入的流程如下：（设插入的非负整数为 $x$）

从高位到低位枚举，假设枚举到第 $i$ 位，显然若 $x$ 的二进制中第 $i$ 位为 $0$ 则 $x$ 不可能插入此处，直接跳过即可。否则：

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

• 若 $A_i=0$，那么：

  1. 让 $x$ 异或上所有满足 $j<i$ 且 $x$ 的二进制中第 $j$ 位为 $1$ 的 $A_j$，这样做是为了保证性质 2.1 中有且仅有 $A_j$ 的二进制第 $j$ 位可能为 $1$ 的性质，所以要通过异或操作把 $x$（未来的 $A_i$） 的这些位删掉，不直接减去 $2^j$ 的原因同上。
  2. 让 $A_i\to x$；
  3. 让所有满足 $j>i$ 的 $A_j$ 都异或上 $A_i$，这样做同样是为了保证性质 2.1 中有且仅有 $A_j$ 的二进制第 $j$ 位可能为 $1$ 的性质；
  4. 结束插入；

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

插入代码如下：

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;
}

查询

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

求 $S$ 有多少个不同的子集异或和为 $x$

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

求 $S$ 的子集的最大异或和

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

代码如下：

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

求 $S$ 的子集的最小异或和

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

代码如下：

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;
}

求 $S$ 的子集的第 $k$ 小异或和

首先线性基中的元素是异或不出 $0$ 的，所以若 $S$ 可以异或出 $0$，即 $has0=true$，那么就需要让 $k\to k-1$。

由于 $A$ 中只有不为 $0$ 的元素才对异或和有贡献，所以不妨用一个数组 $B$ 依次记录下 $A$ 中不为 $0$ 的值。

显然，由于线性基可以异或出 $S$ 能异或出的所有值，所以 $2^{|B|}-1$ 种 $B$ 的非空子序列都可以异或出互不相同的值，所以若 $k>2^{|B|}-1$ 就无解。

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

那么解法就很明显了，把所有满足 $k$ 的二进制中第 $i$ 位为 $1$ 的 $B_i$ 异或起来，我们就能得到 $S$ 的子集的第 $k$ 小异或和。

代码如下：

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;
}

额外的操作

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

合并

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

可持久化

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

upd：2025.06.21

带删除

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

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

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

具体的，每个元素插入的时候额外维护一个 $id_i$ 表示它最后由那些元素组成（即最后变成某个基或者变成 $0$ 时具体异或上了原来插入的哪些元素）。

那么分讨一下，假设删除的是 $x$：

• 如果删除的元素不在线性基中，直接删除即可；
• 否则要消去 $x$ 带来的影响：
  • 若存在一个不在线性基中的元素（插入时被消成了 $0$），满足其 $id$ 包含 $x$，那么 $x$ 将会在这个地方复活，处理一下；
  • 否则秩将会减一，此时：
    • 找到线性基中最小的，$id$ 包含 $x$ 的基 $z$；
    • 将所有 $id$ 包含 $x$ 的基全部异或上 $z$（$z$ 也要异或自己，相当于变成了 $0$）；

这样做显然是对的。