用于接近线性的查询异或相关的问题，如异或前缀和，和别的数的最大异或和等。
01字典树是按照二进制下每一位是0还是1将一些数进行分类，每一个结点的左孩子表示当前这一位是0的所有数，右孩子表示当前这一位是1的所有数，这样递归的分下去总可以把所有的数分类完。

如要求每次线性的回答一个数和一个数组中的所有元素的最大异或值，数组范围是2e5：
将数组中的所有数类似于哈夫曼树一样·按位建成一棵树，如3(0011)，8(1000)，5(0101)那么就可以画出一个这样的树：

1
2
3
4
5
6
7
8
9
10
       root
    /        \
   0          1
 /   \        /	
0     1      0
 \	  /      /
  1  0     0
   \  \   /
    1	1  0
   (3)(5)(8)

那么比如查询这些数和6(0110)异或后的最大值，想要异或完最大，那么就要求每一位都不一样，因为位数越高那么占得权值就越大，所以从前往后贪心，如果树在这个位上有不一样的分支那就往这条分支上走。6的第一位是0，那么要找第一位是1的，查询的时候要选右边的节点，所以确定了答案的第一位是1，然后发现6的第二位是1并且有是0的分支，那么往这条边上走，所以答案的第二位也是1，类似的答案的第三位也是1，但是在第四位的时候没有没有对应的1的分支，也就是说3、5、8中首位是1，第二第三的数字是0的数字中没有第四位是1的那么只能往0这条边上走，所以答案的第四位是0。然后结束查询，答案就是14(1110)。
同样的也可以快速地求出一个数组中最大的连续异或和：
Vampiric Powers, anyone?
大致意思就是一个整数数组长度为m，可以进行任意次下面的操作：
选择一个索引i，然后在这个数组的末端插入一个元素使得数组长度+1,并且这个元素的值是从i到末尾的所有元素的异或之和。
这道题最后分析出来就是求最大连续子段异或和。
证明：假设不要求连续的子段组成的异或和，比如8 2 4 12 1那么显然最大的就是15(8,2,4,1)而不是14。考虑这中情况为什么不合法，非连续的含义可以转化成跳过一些数所得到的异或和，因为异或有归零律，那么只需要证明有三个数的数组c a b按照上述规则能产生跳过a后异或和中带b（即b不被抵消，a被抵消，也就是所有i小于2的异或和中，b的个数是奇数，a的个数是偶数）就能推出这个操作能跳过一些数得到的异或和。那么假设：一开始i选择3，得到c a b b那么就比如i=1的时候想要异或和中带b是不可能的因为只要i小于3那么每次操作得到的异或和中必定带有偶数个b相互抵消(i大于等于3时对于下一步i小于3时，情况和初始或者和i = 3效果是一样的，比如 i = 3c a b b b^b => c a b b 0 => c a b b,i = 4c a b b b => c a b)，所以不可能；一开始i选择2，得到c a b a^b同理以后不管怎么操作也是a和b都是偶数一起被抵消了。所以不要求连续的子段这在这种规则下是不能产生的。
最大连续子段异或和一定是可以被构造出来的，和假设中的第二个构造法类似，比如[l,r]之间的异或和，可以先产生[r+1,m]的所有异或和放到m+1的位置，那么下次只需要选i= l即可把r后面的所有数抵消。
如何快速求出最大连续子段异或和？这道题的范围要求在线性的复杂度内求出。可以先求出异或后缀和sum[i]，注意到[l,r]可以看成sum[l]^sum[r+1]（归零律）就是直接抵消了r后面的数所以对后缀和进行建01字典树，枚举l，找到一个最大的r即可，并且异或有交换律所以就算找到的r小于l也没事。
需要注意的是不一定要找一r有可能l后面的所有数要比找到的r要更小，所以最大值要考虑自己sum[l]本身.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#define int long long
#define N 200005

int n, a[N];
int nxt[N][2],cnt;

void insert(int x){
    int u = 0;
    for(int i = 8;i>=0;--i){
        int y = (x>>i)&1;
        if(nxt[u][y]) u = nxt[u][y];
        else nxt[u][y] = ++cnt,u = nxt[u][y];
    }
}

int find(int x){
    int u = 0,sum = 0;
    for(int i = 8;i>=0;--i){
        int y = (x>>i)&1;
        if(nxt[u][y^1]) sum += (1<<i),u = nxt[u][y^1];
        else u = nxt[u][y];
    }
    return sum;
}

void init(){
    for(int i = 0;i<=cnt;++i) nxt[i][1] = nxt[i][0] = 0;
    cnt = 0;
}

void solve() {
    cin>>n;
    a[0] = 0;
    for(int i = 1;i<=n;++i) cin>>a[i],a[i] ^= a[i-1],insert(a[i]);
    int ans = 0;
    for(int i = 1;i<=n;++i) ans = max({ans,find(a[i]),a[i]});
    cout<<ans<<endl;
}

实际上最大连续异或和实际上也可以用dp。