01trie

01 Trie

字符集为 \(\{0,1\}\) 的字典树 Trie

一般用于解决异或相关问题

基本问题

给定数集 \(S\) 和数 \(x\)，求 \(\max\{x \oplus S_i\}\)。

从高到低将集合 \(S\) 中的数插入 Trie（注意高位要补齐）。

从根节点开始，尽量选和 \(x\) 当前位不同的，计算答案。

容易证明这一定是最大值。

时空复杂度 \(O(|S|\log S_i)\)

int tot=0;
int son[N*35][2];
inline void build(LL x){
	int pos=0;
	for(int i=33;i>=0;i--){
		int bit=(x>>i)&1;
		if(!son[pos][bit]) son[pos][bit]=++tot;
		pos=son[pos][bit];
	}
}
inline LL query(LL x){
	int pos=0;LL ans=0;
	for(int i=33;i>=0;i--){
		int bit=(x>>i)&1;
		if(son[pos][bit^1]) 
			pos=son[pos][bit^1],ans+=(1ll<<i);
		else pos=son[pos][bit];
	}
	return ans;
}

变式 0

给定数集 \(S\) 和数 \(x\)，求 \(\min\{x \oplus S_i\}\)。

很简单，每次尽量选和 \(x\) 当前位相同的就好。

变式 1-1

给定数集 \(S\)，求两两最大异或和。

对每个数都做一次基本问题就好了。

因为自己异或自己是 \(0\)，不影响答案，所以预处理 01Trie，查询取最大值就结束了。

复杂度还是 \(O(|S|\log S_i)\)

变式 1-2

给定序列 \(A\) ，求 \(max_{1\le l\le r\le n}\{A_l \oplus \dots \oplus A_r\}\)。

根据异或的性质，可以推出

\(\begin{aligned} A_l \oplus \dots \oplus A_r& = (A_1 \oplus \dots \oplus A_{l-1})\oplus (A_1 \dots \oplus A_r) \\ & = S_{l-1} \oplus S_r \end{aligned}\)

那么就转化成对于 \(A\) 的前缀和 \(S\) 做变式 1-1。

注意！\(S_0\) 也要加入 Trie！

扩展 1

给定数集 \(S\) 和数 \(x\)，求第 k 大异或和。

类似权值线段树求区间第 k 小的思路。

对 Trie 上每个点，记录子树大小（出现次数），让 k 跟和 x 不同的子树比大小，小就走和 x 不同；大就走和 x 相同，k 减去不同的子树大小。

int tot=0;
int son[N*35][2],siz[N*35];
inline void build(LL x){
	int pos=0;
	for(int i=33;i>=0;i--){
		int bit=(x>>i)&1;siz[pos]++;
		if(!son[pos][bit]) son[pos][bit]=++tot;
		pos=son[pos][bit];
	}
	siz[pos]++;
}
inline LL query(LL x,LL rk){
	int pos=0;LL ans=0;
	for(int i=33;i>=0;i--){
		int bit=(x>>i)&1;
		if(!son[pos][bit^1]) pos=son[pos][bit];
		else if(rk<=siz[son[pos][bit^1]]) 
			pos=son[pos][bit^1],ans|=1ll<<i;
		else rk-=siz[son[pos][bit^1]],pos=son[pos][bit];
	}
	return ans;
}

扩展 1-1

给定数集 \(S\)，求两两第 k 大异或和。

优先队列维护对每个数来说，异或和第 t 大（初始 t 为 1）

每次取出堆顶，将第 t+1 大加入队列。

可以保证第 i 次取到的数是第 i 大。

由于每个异或和会统计两次（两数交换），所以第 2k 次取到的就是答案。

扩展 2

给定一棵带权树，求树上最大异或路径。

（某些人可能就想写树剖了，但你别急

记 \(dis(i,j)\) 代表从点 i 到 j 的路径异或和。

由于根节点到 \(lca(i,j)\) 的路径是重复的，所以 \(dis(i,j)=dis(rt,i)\oplus dis(rt,j)\)。

问题转化成给定数集求两两最大异或和。

01 Trie 是个挺神奇的东西qwq

如果有错误或者不清楚的地方欢迎评论/私信