谔谔，发现线性基其实不需要线性代数的一些概念也很好理解，浅谈一下。
线性基
- 定义
线性基是一个最小的集合，满足集合中任意的异或值的集合与原序列的任意异或值的集合相等。
- 性质
1.原序列的数都可以通过线性基异或得到。
2.线性基中不存在任何的子集的异或值为 \(0\)。（因为如果为 \(0\) 就代表有多余的，不是最小的）
- 实现
先来说一下建立（插入）线性基的过程。（以找序列最大异或和为例）
一些声明：
\(d\) 数组表示线性基的集合， \(x\) 表示原序列现在要插入的数。
\(d_i\) 满足 \(d_i\) 二进制下的第 \(i\) 位是 \(1\)。
注意，要按照线性基最小的原则，每一次插入的要尽可能少。
我们先从二进制来考虑。肯定是要尽可能得把 \(x\) 变成 \(0\)（由上述性质可得）。
首先枚举二进制位。
先想想异或的性质。如果枚举到的这一位的 \(x\) 是 \(0\)就不管它，如果这一位是 \(1\)，则分类讨论。
情况1：\(d_i\) 为 \(0\)。
把 \(d_i=x\)。因为这一位无法变成 \(0\) 了。
情况2：\(d_i\) 不为 \(0\)。
把 \(x^d_i\)，即把这一位的 \(x\) 变成 \(0\) ，接着考虑下一位。
插入操作就差不多了。
接着我们考虑查询。
记答案为 \(res\)。
考虑在线性基集合里进行异或。发现 \(res\) 每一位的 \(1\) 都只会被集合里的数更改一次，那就对于集合里每一个数进行异或，如果异或之后的比原来的结果大就异或。
大概就是这些了。
本人语文水平有限，可能会出现词不达意，表述不清的情况，请见谅。
参考资料
标签：插入,一位,集合,异或,序列,线性 From： https://www.cnblogs.com/infinite2021/p/18288993