线性基

线性基能用logV的空间存储某些数异或能得到的所有数

p[i]:二进制表示，第一个1在第i个位置的数字

构造：

CPP

void insert(long long x){
	for(int i=63;i>=0;i--){
		if((x>>i)&1){
			if(!p[i])	p[i]=x;
			x^=p[i];
		}
	}
}

查询x和这些数能异或出的最大值

CPP

long long query(long long x){
  long long ans=x;
  for(int i=63;i>=0;i--)	ans=max(ans,ans^v[i]);
  return ans;
}

线性基合并时，把其中一个的每个数插入另一个即可

如果是维护树上信息，倍增不需要一段段合并，因为线性基信息合并重复也没事（参考RMQ），只要合并两个就能解决一条链

文章操作