当我们需要维护和向量空间或者异或和有关的东西，可能会用到线性基：
提出问题
【模板】线性基
题意：给一个长为 \(n\) 的序列，问从中任取若干个数，最大的异或和为多少。
这个问题可以直接使用线性基维护，但是我们考虑将这个问题进行加强：
CF1100F Ivan and Burgers
题意：给一个长为 \(n\) 的序列，\(Q\) 次询问，问从 \(a_l,a_{l+1}\dots a_r\) 中选若干个数，异或和最大为多少。
查询从全局查变成了区间查。
如果使用线段树维护，时间复杂度是 \(O(n\log^2V+Q\log n\log^2V)\)。
如果使用猫树维护，时间复杂度是 \(O(n\log n\log V+Q\log^2V)\)。
深入研究
现在我们继续深究性质，看看能否做到更优的复杂度。
我们先想一想，为什么区间查的线性基不能用全局的维护，某种意义上也就是为什么线性基不支持删除。
因为我们并不知道线性基的每一位是由哪些数组成的，比如说，最高位可能是 \(a_1\oplus a_3\oplus a_4\)，或者最低位是 \(a_{114}\oplus a_{514}\)。
这就导致我们并不知道在查区间的时候，能不能选择某一位。
先假定我们的询问区间都是形如 \([l,n]\) 的，考虑如何处理。
我们考虑记录每一位中编号最小的数的下标 \(b\)，比如我们上面那两个例子中，就是 \(1\) 和 \(114\)。
在处理询问 \([l,n]\) 是，我们就扫一遍，如果 \(b\geqslant l\)，我们就按照正常的线性基进行处理，否则就跳过它。
所以，为了保证答案的正确性，我们要上每一位的 \(b\) 尽可能的大，来满足更多的 \(l\)。
现在我们考虑加入一个数的时候如何保证每一位都得到了最大的 \(b\)。
我们维护二元组，分别表示线性基插入的数和它的时间戳。
当这个数某一位为 \(1\) 的时候，考虑线性基中的当前位：如果为空，则直接插入；如果有数，且其时间戳更小，则交换这两个二元组，并将不在线性基中的数异或上另一个。
具体实现如下：
void insert(int a,int tm)
{
for(int i=19;~i;i--)
{
if(a&(1<<i))
{
if(tim[i])
{
if(tim[i]<tm)
{
swap(xxj[i],a);
swap(tim[i],tm);
}
a^=xxj[i];
}
else
{
xxj[i]=a,tim[i]=tm;
return;
}
}
}
return;
}
这样子，我们只需要顺序将所有元素插入，并在每一次插入后处理的 \(r=i\) 的询问即可。
时间复杂度是 \(O((n+Q)\log V)\)。
拓展延申
上述算法是离线的，那能不能在线呢？
由于线性基大小是 \(O(\log V)\) 的，所以我们每次处理都在前一个的复制上进行处理，就不会破坏前面的线性基了，时间复杂度仍然是 \(O((n+Q)\log V)\) 的。
上述算法是静态的，那能不能带修呢？
不知道，但感觉多半不行。