01trie

01trie

定义

01-trie是字符集为0，1的trie，可以维护异或极值，维护异或和

实现

主体仍然是 trie ，维持 \(t\) 数组记录儿子不变。需要因为异或的性质，所以只需要维护加入 0/1 边的奇偶性即可，所以添加 \(w\) 数组记录父节点到该节点的边数。此外因为要统计异或和，所以要在树上统计，用 \(xorv\) 数组记录。本来trie的查询是很简单的（循环）。但是因为这里涉及合并操作，递归使代码更简单。

关于细节：
记录MAXH为0/1串长度，强制将所有串变为MAXH长度

值的修改(pushup)

void pushup(int x){
    w[x] = xorv[x] = 0;
    if(t[x][0]){
        w[x] += w[t[x][0]];
        xorv[x] ^= xorv[t[x][0]]<<1;
    }
    if(t[x][1]){
        w[x] += w[t[x][1]];
        xorv[x] ^= (xorv[t[x][1]]<<1) | (w[t[x][1]]&1);
    }
    w[x] &= 1;
}

插入&删除

从低到高加入位

void insert(int &x,int v,int dep){
    if(!x)x=mknode();
    if(dep==MAXH)w[x]++;
    else{
        insert(t[x][v&1],v>>1,dep+1);
        pushup(x);
    }
}

void erase(int x, int v, int dep) {
	if(dep==MAXH)w[x]--;
	else{
		erase(ch[x][x&1],x>>1,dep+1);
		pushup(x);
	}
}

全局加一

二进制加一就是指找到从低到高的第一个0，把他置为1，把这个1前面的所有1置为0

100000111+1=100001000

void addall(int x){
    swap(t[x][0],t[x][1]);
    if(t[x][0])addall(t[x][0]);
    pushup(x);
} 

01trie 合并

类似线段树合并

int merge(int a,int b){
    if(!a)return b;
    if(!b)return a;
    w[a] += w[b];
    xorv[a] ^= xorv[b];
    t[a][0] = merge(t[a][0],t[b][0]);
    t[a][1] = merge(t[a][1],t[b][1]);
    return a;
}

思想总结

对于异或和问题，要使用位运算按位解决（傻子都知道）。0/1trie是解决该问题的一种方法，把数字转换成字串是关键一步，随后对于 \(w,xorv\) 数组的维护需要注意细节。最具有技巧性的是全局加一，要对于位运算有深刻的理解。最后，要注意线段树，trie与0/1trie的关系，同为高级数据结构，互相有相同之处。作为OI选手要对其融会贯通。

习题巩固

[省选联考 2020 A 卷] 树 Luogu [省选联考 2020 A 卷] 树 Uoj 提示 0/1trie合并，全局加一

最长异或路径 提示 0/1trie维护极值，贪心