01-trie是指字符集为 \(\{0,1\}\) 的 trie。01-trie 可以用来维护一些数字的异或和，支持修改（删除 + 重新插入），和全局加一（即：让其所维护所有数值递增 \(1\)，本质上是一种特殊的修改操作）。
如果要维护异或和，需要按值从低位到高位建立 trie。
如果要维护异或和，我们只需要知道某一位上 \(0\) 和 \(1\) 个数的奇偶性即可，也就是对于数字 \(1\) 来说，当且仅当这一位上数字 \(1\) 的个数为奇数时，这一位上的数字才是 \(1\)，请时刻记住这段文字：如果只是维护异或和，我们只需要知道某一位上 \(1\) 的数量即可，而不需要知道 trie 到底维护了哪些数字。
插入
像普通 trie 树一样建树即可，只不过边上存的不是字母，是第 \(i\) 为 \(0/1\)。需要注意的是因为每个数的二进制位数可能不同，所以一般有两种解决方法：
第一种为将二进制数倒过来存，第 \(i+1\) 层表示
x>>i&1的值，我习惯叫做低位trie。
第二种为在二进制数前补 \(0\)，从高位到低位建出trie，我习惯叫做高位trie。
点击查看代码
void insert(int x){//高位trie代码，低位trie只需将for循环变为由小到大即可
int u=1;
for(int i=K;i>=0;i--){
int v=x>>i&1ll;
if(!ch[u][v])ch[u][v]=++cnt;
u=ch[u][v];
num[u]++;//存出现次数
}
val[u]=x;
}
删除
因为不可能撤回之前的操作，所以只考虑减少每个点的出现次数，当一个点出现次数为 \(0\) 时，trie 树上以它为根的子树中的点出现次数肯定为 \(0\)。
点击查看代码
void del(int x){
int u=1;
for(int i=K;i>=0;i--){
int v=x>>i&1ll;
u=ch[u][v];
num[u]--;
}
}
询问异或最大值
这个询问既可以是给定一个值 \(x\) 求从集合中选出一个数 \(y\)，求 \(x\oplus y\) 的最大值，也可以是从集合中找到 \(x,y\) 两个数，求 \(x\oplus y\) 的最大值。
求异或最大值本质上是一个贪心的过程，在向低位搜索的过程中，若能取反就取反，不能取反才取正，因为是向低位搜索并贪心，所以只能使用高位trie。
点击查看代码
int querymax(int x){/*贴的是给定x求集合中的数与x异或的最大值
求集合内任意两个数最大值方法一样*/
int u=1;
for(int i=K;i>=0;i--){
int v=x>>i&1ll;
if(ch[u][v^1]&&num[ch[u][v^1]])u=ch[u][v^1];
else u=ch[u][v];
}
return x^val[u];
}
进行全局 \(+1\) 操作
考虑到二进制的加法是怎么实现的，最低位 \(+1\)，然后从低位开始一连串的 \(1\) 由 \(1\) 变成 \(0\)，交换 \(u\) 的左右儿子，然后走左儿子，若没有该儿子，则说明 \(+1\)操作结束了，因为从低位开始，所以只能使用 `低位trie 。
点击查看代码
void update(){
int u=1;
for(int i=0;i<K;i++){
if(!u){
return;
}
num[u]-=num[ch[u][0]];
num[u]+=num[ch[u][1]];
swap(ch[u][0],ch[u][1]);
u=ch[u][0];
}
}
01trie 合并
像线段树一样合并即可。
点击查看代码
int merge(int u,int v){
if(!u||!v){
return u|v;
}
num[u]+=num[v];
ch[u][0]=merge(ch[u][0],ch[v][0]);
ch[u][1]=merge(ch[u][1],ch[v][1]);
}
同理也可以进行可持久化合并。
点击查看代码
int merge(int u,int v){
if(!u||!v){
return u|v;
}
p=++cnt;
ch[p][0]=merge(ch[u][0],ch[v][0]);
ch[p][1]=merge(ch[u][1],ch[v][1]);
return p;
}
例题
[省选联考 2020 A 卷] 树
考虑 \(val_u\) 怎么求出来的。将组成 \(val_v(v\in son_u)\) 的数全部 \(+1\)，然后进行异或，最后异或上 \(c_u\)。考虑每个点建一颗 trie，存储每个点的 val 中某一位出现了多少个 \(1\)。将 \(c_u\) 插入 \(u\) 的 trie 中，计算出 \(val_u\) 后将这棵 trie 整体 \(+1\) 后，合并到 \(fa_u\) 的 trie 树中。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=6e5+10,K=22;
struct node{
int ch[2],cnt;
}p[N*K];
vector<int>e[N];
int cnt_c[N][K],idx;
int n,rt[N],V[N],val[N];
void ins(int x,int st,int u){
int now=st;
for(int i=0;i<K;i++){
int s=(x>>i)&1;
cnt_c[u][i]+=s;
if(!p[now].ch[s]){
p[now].ch[s]=++idx;
}
now=p[now].ch[s];
p[now].cnt++;
}
}
int merge(int u,int v){
if(!u||!v){
return u|v;
}
p[u].cnt+=p[v].cnt;
p[u].ch[0]=merge(p[u].ch[0],p[v].ch[0]);
p[u].ch[1]=merge(p[u].ch[1],p[v].ch[1]);
return u;
}
void update(int st,int u){
int now=st;
for(int i=0;i<K;i++){
if(!now){
return;
}
cnt_c[u][i]+=p[p[now].ch[0]].cnt;
cnt_c[u][i]-=p[p[now].ch[1]].cnt;
swap(p[now].ch[0],p[now].ch[1]);
now=p[now].ch[0];
}
}
void dfs(int u){
rt[u]=++idx;
ins(V[u],rt[u],u);
for(auto v:e[u]){
dfs(v);
merge(rt[u],rt[v]);
for(int j=0;j<K;j++){
cnt_c[u][j]+=cnt_c[v][j];
}
}
for(int i=0;i<K;i++){
val[u]+=(1<<i)*(cnt_c[u][i]&1);
}
update(rt[u],u);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
read(n);
for(int i=1;i<=n;i++){
read(V[i]);
}
for(int i=2,fa;i<=n;i++){
read(fa);
e[fa].pb(i);
}
int ans=0;
dfs(1);
for(int i=1;i<=n;i++){
ans+=val[i];
}
write_endl(ans);
return 0;
}