01 Trie：最大异或对、前缀异或与树上路径

一、暴力枚举的痛点：异或的“非单调性”迷局

场景：给定 $n$ 个非负整数 $a_1, a_2, \dots, a_n$ ，要求从中任选两个不同位置的数 $a_i, a_j$ （ $i \neq j$ ），使得它们的按位异或值 $a_i \oplus a_j$ 最大。

暴力解法 ( $O(n^2)$ )：双重循环两两枚举配对。当 $n = 10^5$ 时，配对次数达到 $\frac{10^5 \times 10^5}{2} \approx 5 \times 10^9$ ，考场上必死无疑。

1. 为什么排序贪心彻底失效？

许多同学在初学时会有个直觉：“要让结果最大，是不是找数组里最大的两个数，或者数值差距最大的两个数？”

异或运算（^，数学符号 $\oplus$ ：相同得 0，不同得 1）最反直觉的地方就在于它的非单调性：数值最大的数，绝不意味着它是最佳搭档！

直观例子：假设池子里已经存了三个数，只看低三位二进制：

$3 = (011)_2$
$5 = (101)_2$
$6 = (110)_2$

现在新来了一个数 $x = 2 = (010)_2$ ，让它和池子里的每个数异或：

$2 \oplus 6 = (010)_2 \oplus (110)_2 = (100)_2 = 4$
$2 \oplus 5 = (010)_2 \oplus (101)_2 = (111)_2 = 7$
$2 \oplus 3 = (010)_2 \oplus (011)_2 = (001)_2 = 1$

数值最大的 $6$ 遇上 $2$ 只能凑出 $4$ ；反而是稍微小一点的 $5$ ，和 $2$ 撞出了满分答案 $7$ ！

核心渴望：异或想要变大，根本不看对方的绝对大小，而是看对方能不能在二进制上和自己处处唱反调。我们需要的是：从最高二进制位开始，尽量让异或结果的靠左高位尽可能多地拿到 $1$ 。

二、01 Trie 的物理模型：把整数拍扁成定长二进制串

本节沿用《字典树》中“共享前缀、沿边找数”的思路。在那份小写字母 Trie 中，每个节点最多有 26 个子节点，代表字母 'a' 到 'z'。

如果把整数写成二进制，它就是一个只由 '0' 和 '1' 组成的特殊字符串。每个节点的分叉树枝就缩减成了两个：0 和 1。这就是 01 Trie。

1. 为什么必须严格对齐前导零？

普通字符串 Trie 允许长短不一的单词（如 a 和 about），但 01 Trie 严禁长短不一！

在本讲中，我们统一处理范围在 $[0, 2^{31}-1]$ 内的非负整数。每个整数在二进制下统一补齐为 31 位（从高到低的位权为 $2^{30}, 2^{29}, \dots, 2^0$ ，对应位编号为 $30 \to 0$ ）。

物理意义：Trie 树的层数必须与二进制位权强行锚定。根节点出发的第一步（深度 1），必须所有数字都在表决第 30 位；第二步表决第 29 位……如果不对齐前导零， $3$ 从第 1 位开始建， $5$ 从第 2 位开始建，层数就失去了“当前位权是多少”的物理基准，比对也就彻底报废。

2. 节点的物理表示与特性

用 ch[p][0] 和 ch[p][1] 记录节点 $p$ 指向字符 0 和 1 的子节点编号。
根节点固定为 0，全局分配器 tot 从 $1$ 开始动态开点。当 ch[p][b] == 0 时，说明当前前缀分支尚未开辟。
无需结束标记：在字符串字典树中，为了区分 cat 和 catalog，通常要在末尾打上 is_end 标记。但在 01 Trie 中，每个整数都被强制拉长到了恰好 31 层，走到叶子必定对应一个完整的数，完全不需要额外的标记数组。

三、贪心检索的核心机理：高位的一票否决权

给定一个数 $x$ ，怎么在已经插入 01 Trie 的数字池中，为它挑选出异或值最大的搭档？

1. 为什么高位可以“一票否决”？

我们在第 $k$ 位上，看到 $x$ 的当前位是 $b$ ，我们极度渴望走相反的分支 $b \oplus 1$ （因为不同得 1）。

此时学生常有顾虑：“如果我现在贪心走了 $b \oplus 1$ ，虽然保住了这一位的 $1$ ，但会不会导致后面的路全走错，后面全拿到 $0$ ，因小失大？”

答案是：绝对不会！这就是二进制世界里的降维打击定理：

2^k > \sum_{i=0}^{k-1} 2^i = 2^k - 1

第 $k$ 位的权值是 $2^k$ 。哪怕后面的 $k-1$ 位到第 $0$ 位全部颗粒无收（全是 $0$ ），后面的总价值加起来也只有 $2^k - 1$ ，根本无法撼动第 $k$ 位拿到 $1$ 所确立的绝对优势！

因此，高位拥有绝对的一票否决权。只要有相反分支，闭着眼睛必须走相反分支；只有相反分支不存在时，才委曲求全走同向分支。

2. 严谨检索步步推导

必须时刻牢记：我们是在已有前缀的约束下往下走。选定高位分支后，候选数被锁定在这个子树内，绝不能跨子树去拼凑一个拼装怪！

回顾前面的例子：已插入 $3(011)_2, 5(101)_2, 6(110)_2$ ，查询 $x = 2 = (010)_2$ （省略更高位的全 0）：

考察第 2 位： $x$ 的该位是 0。我们渴望相反位 1。
- 检查 ch[p][1]：分支存在（包含了 $5, 6$ 这两个数）。
- 果断走向 1 分支，当前异或答案的第 2 位锁定为 1。
考察第 1 位： $x$ 的该位是 1。我们渴望相反位 0。
- 检查当前节点下的 ch[p][0]：分支存在（此时只剩下 $5$ 满足高位为 $10$ ）。
- 果断走向 0 分支，当前异或答案的第 1 位锁定为 1。
考察第 0 位： $x$ 的该位是 0。我们渴望相反位 1。
- 检查当前节点下的 ch[p][1]：分支存在（正是数 $5$ 的末位）。
- 走向 1 分支，当前异或答案的第 0 位锁定为 1。

最终我们走到的搭档是 $5(101)_2$ ，累积得到的最大异或和是 $(111)_2 = 7$ 。

易错陷阱：在树上走过的边，代表的是搭档自身包含的二进制位（ $1 \to 0 \to 1$ ），而不是最终异或出来的结果位（ $1 \to 1 \to 1$ ）。边记录搭档，结果累加到答案中，切莫本末倒置。

01 Trie存有011、101、110，查询010时按高位优先选择搭档101，异或结果111=7；高亮边标的是搭档位101，不是结果位111。

四、核心模板实现一：最大异或对

场景：输入一个整数 $n$ ，随后的 $n$ 个数中选出两个不同位置的数，使得异或和最大。范围： $2 \le n \le 10^5$ ， $0 \le a_i < 2^{31}$ 。

1. 巧妙的动态插入：边查边插，别凭空加零

这里只求最大值、且 $n\ge2$ ，先把所有数插入再查询也是对的：自身异或为 0，不会压过更大的合法答案；如果所有数都相同，不同位置也能得到 0。不过第九节改成计数时，这样做就会多算自身和重复的数对。

因此我们统一养成边查边插（增量法）的习惯：

先把第一个数 $a_1$ 插入树中；
遍历到第 $i$ 个数时（ $i \ge 2$ ）：先向 Trie 查询它与前 $i-1$ 个数配对的最大异或值，更新全局最大值；
查完后，再把 $a_i$ 自己插入树中。

这样不仅天然保证了选出的两个数必定来自不同下标，而且对于任意下标对 $(i, j)$ （设 $i < j$ ），在处理到 $j$ 时 $i$ 一定已经在树中守株待兔了，绝不漏掉最优解！

同时切忌在开头盲目先 ins(0)，如果数组里本没有 0，凭空插入假零会引入合法的伪候选，直接摧毁极端数据的正确性（例如输入两个 $5$ ，本应得到 $0$ ，塞了假零就会错误输出 $5$ ）。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005, B=30;

// 节点编号用 32 位整型防 MLE：N * 32 约为 3.2e6，long long 下开销翻倍易卡内存
int32_t ch[N*(B+2)][2], tot;

// 插入一个 31 位非负整数
void ins(int x){
	int p=0;
	for(int k=B;k>=0;k--){
		int b=(x>>k)&1;
		if(!ch[p][b]) ch[p][b]=++tot;
		p=ch[p][b];
	}
}

// 查询与 x 异或能得到的最大值
int query(int x){
	int p=0, res=0;
	for(int k=B;k>=0;k--){
		int b=(x>>k)&1;
		// 贪心：优先走相反位 b ^ 1
		if(ch[p][b^1]){
			res|=(1LL<<k);
			p=ch[p][b^1];
		}else{
			p=ch[p][b];
		}
	}
	return res;
}

void solve(){
	int n;
	if(!(cin>>n)) return;
	int x, ans=0;
	cin>>x;
	ins(x); // 先存第一个数，树非空且绝不引入外部假零
	for(int i=2;i<=n;i++){
		cin>>x;
		ans=max(ans,query(x)); // 查旧数
		ins(x);                // 录入自己
	}
	cout<<ans<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

复杂度分析：

时间复杂度：每个数插入与查询都走满恒定的 31 步，总时间复杂度为 $O(31n)$ ；当 $n=10^5$ 时，插入与查询合计约走 $6.2\times10^6$ 层，实际耗时取决于机器和实现。
空间复杂度：每个数最多新开 31 个节点，总节点数不超过 $31n$ 。全局静态数组占用空间约为 $31n \times 2 \times 4\text{ 字节} \approx 24.8\text{ MB}$ ，安全稳妥。

五、跨越维度：树上异或路径的“消消乐”降维拆解

现在将问题从线性数组推向树形结构：

实战模型：给定一棵含 $n$ 个节点的树，边上带有非负权值 $w$ 。定义两点 $u, v$ 之间的路径权值为路径上所有边权的异或和。求整棵树上任意两点间路径异或和的最大值。

如果任选两点暴力跑 DFS 找路径，复杂度是不可接受的 $O(n^3)$ 或 $O(n^2)$ 。

1. 异或的核心物理性质：自反性与消消乐

回忆普通树上前缀和：两点 $u, v$ 之间的路径长度为 $dist(u) + dist(v) - 2 \times dist(\text{LCA}(u, v))$ 。不仅要做减法，还必须死磕求最近公共祖先（LCA）。

但异或运算拥有绝妙的自反性：

x \oplus x = 0, \quad x \oplus 0 = x

任何数值只要被连续异或两次，就会自动灰飞烟灭！

2. 灵魂数组：`d[u]`

任意选定树上的节点 $1$ 为根节点，定义灵魂数组 d[u]：

物理意义：从根节点 $1$ 到节点 $u$ 的唯一下行路径上，所有边权的异或和。

显然有递推关系：

$d[1] = 0$ （根节点无需经过任何边）
若节点 $u$ 到子节点 $v$ 存在一条权值为 $w$ 的边，则：
$d[v] = d[u] \oplus w$

3. 剥洋葱：为什么 LCA 在异或面前彻底失效？

考察树上任意两点 $u$ 和 $v$ 。它们在树上的实际简单路径，一定会经过它们的最近公共祖先 $\text{LCA}(u, v)$ 。

根到 $u$ 的路径可被剖开为两截： $(root \to \text{LCA}) \text{ 和 } (\text{LCA} \to u)$
根到 $v$ 的路径同样剖开为两截： $(root \to \text{LCA}) \text{ 和 } (\text{LCA} \to v)$

现在直接将 $d[u]$ 和 $d[v]$ 异或在一起：

d[u] \oplus d[v] = (root \to \text{LCA}) \oplus (\text{LCA} \to u) \oplus (root \to \text{LCA}) \oplus (\text{LCA} \to v)

看！公共前缀段 $(root \to \text{LCA})$ 出现了整整两次！根据自反性，它直接被自己消去：

d[u] \oplus d[v] = (\text{LCA} \to u) \oplus (\text{LCA} \to v) = xorpath(u, v)

这简直是降维打击！求树上两点异或和，根本不需要求 LCA，甚至不需要知道 LCA 是谁。两点路径异或值，就是它们各自根前缀的异或值！

4. 手推验证一棵小树

树的边权如下： $(1, 2, 3), (2, 3, 4), (2, 4, 6)$

$d[1] = 0$
$d[2] = d[1] \oplus 3 = 3$
$d[3] = d[2] \oplus 4 = 3 \oplus 4 = 7$
$d[4] = d[2] \oplus 6 = 3 \oplus 6 = 5$

现在要求 $3$ 到 $4$ 的路径异或和：

物理真实路径为 $3 \to 2 \to 4$ ，经过边权 $4$ 和 $6$ ， $4 \oplus 6 = 2$ 。
用根前缀计算： $d[3] \oplus d[4] = 7 \oplus 5 = 2$ ！
公共边 $(1, 2)$ 的边权 $3$ 在两端都参与了一次，完美互相抵消。

全树的最大异或路径，瞬间退化为：在数组 $[d[1], d[2], d[3], d[4]] = [0, 3, 7, 5]$ 中，找出两个元素的最大异或对！ 最优搭档是 $d[1]=0$ 与 $d[3]=7$ ，异或得到 $7$ ，对应从节点 $1$ 到 $3$ 的路径。

换根会影响答案吗？ 绝不会！若改以 $2$ 为根，所有点的 $d$ 值仅仅是整体异或了一个常数 $C = 3$ 。任意两个点再相异或时，常数 $C$ 又被抵消两次，差值保持原样。

六、核心模板实现二：树上最长异或路径 (洛谷 P4551)

场景：给定一棵含 $n$ 个节点的带权无向树。输入：第一行点数 $n$ （ $1 \le n \le 10^5$ ），随后 $n-1$ 行每行三个整数 $u, v, w$ （ $1 \le u, v \le n, 0 \le w < 2^{31}$ ）。输出：整棵树中最大的两点路径边权异或值。

1. 算法保障：非递归 BFS 迭代遍历

题目保证是树，但树的形态可能退化为一条长链（深度达 $10^5$ ）。如果写普通的递归 DFS，在评测机默认栈空间较小时可能瞬间爆栈（Runtime Error / SIGSEGV）。我们使用手写队列 q 进行 BFS 遍历，绝对杜绝爆栈风险。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005, B=30;

struct Edge{int v,w;};
vector<Edge> g[N];
int fa[N], q[N], d[N];
int32_t ch[N*(B+2)][2], tot;

void ins(int x){
	int p=0;
	for(int k=B;k>=0;k--){
		int b=(x>>k)&1;
		if(!ch[p][b]) ch[p][b]=++tot;
		p=ch[p][b];
	}
}

int query(int x){
	int p=0, res=0;
	for(int k=B;k>=0;k--){
		int b=(x>>k)&1;
		if(ch[p][b^1]){
			res|=(1LL<<k);
			p=ch[p][b^1];
		}else{
			p=ch[p][b];
		}
	}
	return res;
}

void solve(){
	int n;
	if(!(cin>>n)) return;
	for(int i=1;i<n;i++){
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back({v,w});
		g[v].push_back({u,w});
	}
	
	// 1. BFS 迭代遍历树，防止长链深递归爆栈
	int head=0, tail=0;
	q[tail++]=1;
	fa[1]=0;
	d[1]=0;
	while(head<tail){
		int u=q[head++];
		for(auto e:g[u]){
			int v=e.v, w=e.w;
			if(v==fa[u]) continue;
			fa[v]=u;
			d[v]=d[u]^w; // 核心推导：前缀异或转移
			q[tail++]=v;
		}
	}
	
	// 2. 将树上问题转化为 d 数组的最大异或对
	int ans=0;
	ins(d[1]); // 这里的 d[1]=0 是真实前缀，代表以根为端点的路径可能
	for(int i=2;i<=n;i++){
		ans=max(ans,query(d[i]));
		ins(d[i]);
	}
	cout<<ans<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

七、区间异或的降维：前缀和的完美迁移

场景：求一个数组的连续子段 $a[l \dots r]$ ，使得该子段内所有元素的异或和最大。

前缀异或的抵消原理见《前缀和与差分》第五节。这里直接接上它的结论：令 $s[0]=0$ 、 $s[i]=s[i-1]\oplus a[i]$ ，区间 $[l,r]$ 的异或和就是 $s[r]\oplus s[l-1]$ 。

这又是一次降维打击：寻找异或和最大的子段，等价于在 $s$ 数组中寻找一对 $s[r]$ 和 $s[l-1]$ （要求 $l-1 < r$ ），使得它们的异或值最大！

实现要点：先插入 s[0]=0，再依次用 s[r] 查询并插入。这里的 0 是真实的空前缀，代表子段可以从第 1 个元素开始，不是第四节提醒的“假零”。

八、选学：滑动窗口与 01 Trie 的“引用计数”删除法

场景：如果题目加上了限制，要求选出的子段长度不超过 $m$ 怎么办？

此时 $r - (l-1) \le m$ ，即 $l-1 \ge r-m$ 。对于当前的 $s[r]$ ，合法搭档是下标位于 $[\max(0,r-m),r-1]$ 内的前缀异或值，不是按异或值大小划出的区间。随着 $r$ 的向右滑动，窗口不仅要吃进新的 $s[r-1]$ ，还必须吐出过期的 $s[r-m-1]$ （前提是 $r-m-1 \ge 0$ ）。

物理痛点：普通 01 Trie 怎么删除一个数？绝不能直接把经过的节点清零！因为很多数在前面高位是共享前缀路径的。你把过期数字的树枝砍了，还在保质期内的其他数字也会跟着遭殃。

引用计数法（灵魂数组 cnt）：给每个节点增加一个 cnt 属性，记录“当前有多少个有效的数经过了这个节点”。

插入：沿途经过的所有节点 cnt[p]++。
删除：沿途经过的所有节点 cnt[p]--。

查改机制同步升级：在贪心往下走时，我们不能仅仅看指针是否存在，还要看存活数量是否大于 0。

下面沿用第四节的 ch、tot、N、B，另加全局数组 int32_t cnt[N*(B+2)];。modify 替换原来的 ins；后面的 if/else 片段则替换 query 循环内原有的分支判断。只删除仍在窗口中的数，并在窗口非空时调用 query。

// 带有引用计数的插入与删除合并写法（val传入 1 表示插入，-1 表示删除）
void modify(int x, int val) {
	int p = 0;
	for (int k = B; k >= 0; k--) {
		int b = (x >> k) & 1;
		if (!ch[p][b]) ch[p][b] = ++tot;
		p = ch[p][b];
		cnt[p] += val; // 沿途更新存活数字的个数
	}
}

// 查询操作的条件升级
if (ch[p][b ^ 1] && cnt[ch[p][b ^ 1]] > 0) { // 必须还有活口
	res |= (1LL << k);
	p = ch[p][b ^ 1];
} else {
	p = ch[p][b];
}

九、选学：高位分支计数——统计异或值小于 K 的对数

场景：给定数组，统计有多少对 $(i, j)$ 满足 $i < j$ 且 $a_i \oplus a_j < K$ 。

最大值/最小值问题靠“贪心”，而计数问题则要靠“分叉包揽”。我们依然利用刚才建立的 cnt 数组。当我们拿着 $x$ 在树上从高到低寻找搭档时，面对第 $k$ 位，我们考察 $x$ 的当前位 $b$ ，以及限制条件 $K$ 的当前位 $k_b$ 。

核心分岔逻辑推导：

如果限制位 $k_b = 1$ ：
- 如果我们让异或结果的这一位变成 0，那么不管后面低位长什么样，结果已经绝对小于 $K$ ！
- 怎么让异或结果变 0？必须选和 $b$ 相同的分支（即走 $b$ ）。所以，我们直接把 $b$ 分支里的 cnt 全部加到答案里：ans += cnt[ch[p][b]]。
- 然后，如果我们要继续保持悬念（异或结果的这一位等于 $K$ 的 1），就必须走相反分支 $b \oplus 1$ ，进入下一层继续比对。
如果限制位 $k_b = 0$ ：
- 异或结果的这一位绝对不能是 1，否则直接超标。
- 因此我们毫无选择，必须让异或结果等于 0（走 $b$ 分支），进入下一层继续比对。相反分支 $b \oplus 1$ 连看都不用看。

1. 手推验证一票否决的威力

假设树里存有三个数： $4(100)_2, 5(101)_2, 6(110)_2$ 。我们查询 $x = 2 = (010)_2$ ，求有多少个数与它异或 $< K = 5 = (101)_2$ 。

第 2 位（权重 4）： $x$ 该位为 0， $K$ 该位为 1。
- 要想直接比 $K$ 小，走 0 分支。但树里没有首位为 0 的数，ans += 0。
- 保持悬念，走 1 分支（4、5、6 都在这里）。
第 1 位（权重 2）： $x$ 该位为 1， $K$ 该位为 0。
- $K$ 为 0，我们必须让异或出 0。于是强制走 1 分支（ $1 \oplus 1 = 0$ ）。
- 分支 1 里只有 $6(110)_2$ 。数字 4 和 5 都在分支 0 里，直接被淘汰！
第 0 位（权重 1）： $x$ 该位为 0， $K$ 该位为 1。
- 要想直接比 $K$ 小，走 0 分支。分支 0 指向末尾是 0 的数（正是刚才留下的 6）。
- 获取其存活数量：ans += 1。
- 保持悬念走 1 分支，但为空。

最终得到 1 个合法数。手算验证： $6 \oplus 2 = 4 < 5$ ，完全正确！

2. 完整核心代码：统计合法对数

// 独立验证题：给定 n 个数和 K，求满足 a_i ^ a_j < K 且 i < j 的对数。
// 范围：1 <= n <= 100000, 0 <= a_i, K <= 10^9。（K=0 时严格小于的对数必定为 0）
// 输入：第一行 n 和 K。第二行 n 个数。
// 样例输入：
// 4 5
// 4 5 6 2
// 样例输出：
// 4 
// (合法对为：(4,5)异或1，(4,6)异或2，(5,6)异或3，(6,2)异或4，共 4 对)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005, B=30;

int32_t ch[N*(B+2)][2], tot;
int32_t cnt[N*(B+2)]; // 灵魂数组：记录经过该节点的数字个数

void ins(int x){
	int p=0;
	for(int k=B;k>=0;k--){
		int b=(x>>k)&1;
		if(!ch[p][b]) ch[p][b]=++tot;
		p=ch[p][b];
		cnt[p]++; // 记录数字存活个数
	}
}

// 核心查询逻辑：在已有的 Trie 中，找出与 x 异或结果严格小于 limit 的数字个数
int query_less_than(int x, int limit){
	int p=0, res=0;
	for(int k=B;k>=0;k--){
		int b=(x>>k)&1;
		int limit_b=(limit>>k)&1;
		
		if(limit_b == 1){
			// 结果填 0 绝对小于 limit：走 b 分支
			if(ch[p][b]) res += cnt[ch[p][b]];
			// 结果填 1 保持悬念：走 b^1 分支继续
			p = ch[p][b^1];
		} else {
			// limit该位是 0，结果必须填 0 才能维持不超标：只能走 b 分支
			p = ch[p][b];
		}
		
		if(!p) break; // 放在步进之后判断：如果后续路径断了，提前结束
	}
	// 注意：求的是“严格小于”，如果是 <=，还需要在最后加上 res += cnt[p]
	return res;
}

void solve(){
	int n, K;
	if(!(cin>>n>>K)) return;
	int ans=0;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		// 边查边插：利用之前插入的数，避免重复配对和自身配对
		ans += query_less_than(x, K);
		ins(x);
	}
	cout<<ans<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

十、渐进式实战练习题单

第一阶段：01 基础与贪心建树

洛谷 P10471 最大异或对 The XOR Largest Pair
- 破题指引：01 Trie 的起手试金石。深刻理解高位贪心的无后效性，以及边查边插的动态维护逻辑，杜绝自我配对。

第二阶段：树上与区间前缀转化

洛谷 P4551 最长异或路径
- 破题指引：本讲核心例题。利用 $x \oplus x = 0$ 砍断树上 LCA 的束缚，将整棵树拍扁为一维前缀数组 d。
Codeforces 282E Sausage Maximization（洛谷题号 CF282E）
- 破题指引：这题求的是不相交前缀与后缀的异或最大值，不是第七节的普通最大连续子段异或。枚举两部分的分界，维护合法前缀的异或值，再拿后缀异或值到 Trie 中查询；注意保证前后两段不重叠，位数也要按原题数值范围调整。

第三阶段：带修、可持久化与综合进阶（省选级）

洛谷 P4735 最大异或和（拓展，本套未展开）
- 破题指引：引入带有区间限制的异或查询，需要给 01 Trie 引入版本历史，进化为可持久化 01 Trie。这是掌握本篇静态结构后的后续方向，本套不展开版本维护与查询细节。

01 Trie