放上大佬博客（除了在线删除基本都能学会。。。）
线性基详解_a_forever_dream的博客-CSDN博客_线性基
题表
P4570 [BJWC2011]元素
根据性质，线性基维护最少的数字，则最终答案选出石头的个数是固定的。对于一个随机出来的答案，当我们找到一个能使当前答案增加但无法放进去的额外石头时，可以将答案中最小的那个石头进行交换。那我们可以一开始以石头权值排序，则能得到答案。
P3857 [TJOI2008]彩灯
题意使求线性基能维护的异或值的值域，可以想到求第k小值时利用的按位思想，即可以明白2^{线性基的集合个数}即为答案
CF1100F Ivan and Burgers
求区间的最大异或和。
很容易想到的方法是线段树维护线性基，但是复杂度多一个log
借鉴了大神博客的nlogn
我们可以先把询问离线，按询问的右端点排序，然后逐个遍历1到n每个元素，维护一个线性基，这个线性基维护一个数组pos[i]，表示d[i]有值时的下标最大的点。每次插入时，维护线性基中每个位置的pos即可。这样在询问时，如果这一位的pos比询问的左端点大，代表这个d在l之后是合法的，d便可以用，贪心找最大值即可。
1 inline void modify(int x,int l){
2 for(int j=20;j>=0;--j)
3 if(x&bin[j]){
4 if(!d[j])return pos[j]=l,d[j]=x,void();
5 if(pos[j]<l)swap(pos[j],l),swap(x,d[j]);
6 //这里优点质疑线性基的正确性
7 //现在不质疑了可以看成，维护此时的线性基
8 //一开始是空的插入一个x
9 //然后再把之前的上一个线性基的数据插入进来
10 //所以线性基的正确性有保护
11 x^=d[j];
12 }
13 return ;
14 }
15 inline int query(int l){
16 int ans=0;
17 for(int j=20;j>=0;--j)
18 if((ans^d[j])>ans&&pos[j]>=l)
19 ans^=d[j];
20 return ans;
21 }
事实上预处理到每个r的线性基即可实现在线询问
P3292 [SCOI2016]幸运数字
有了上题的基础，这题直接按从祖先到每个点为序列，预处理线性基，在线询问即可