线性基

· · 个人记录

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

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

构造：

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和这些数能异或出的最大值

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），只要合并两个就能解决一条链