前言（吐槽）

其实我是一直知道这玩意，但一直没学过。最近重新在看字符串算法，其中有一节讲到字典树可以处理位异或运算

知道原理但没手写过，结果隔天的练习赛就遇到了一题。。。（该来的还是会来的）

开始吐槽~~(其实是学习和抄板子)~~

板子

01-trie 是指字符集为 ${0,1}$ 的字典树。常用来维护数组的异或极值和异或和。

01-trie 支持修改（删除 + 重新插入），和全局加一（即：让其所维护所有数值递增 1，本质上是一种特殊的修改操作）。

这里先上个简单的板子

int tol; //节点个数 
LL val[32*MAXN]; //点的值 
int ch[32*MAXN][2]; //边的值 
 
void init(){ //初始化 
    tol=1;
    ch[0][0]=ch[0][1]=0;
}
 
void insert(LL x){ //往 01字典树中插入 x 
    int u=0;
    for(int i=32;i>=0;i--){
        int v=(x>>i)&1;
        if(!ch[u][v]){ 
            //如果节点未被访问过 
            ch[tol][0]=ch[tol][1]=0; //将当前节点的边值初始化 
            val[tol]=0; //节点值为0，表示到此不是一个数 
            ch[u][v]=tol++; //边指向的节点编号 
        }
        u=ch[u][v]; //下一节点 
    }
    val[u]=x; //节点值为 x，即到此是一个数 
}
 
LL query(LL x){ //查询所有数中和 x异或结果最大的数 
    int u=0;
    for(int i=32;i>=0;i--){
        int v=(x>>i)&1;
        //利用贪心策略，优先寻找和当前位不同的数 
        if(ch[u][v^1]) u=ch[u][v^1];
        else u=ch[u][v];
    }
    return val[u]; //返回结果 
}

观察建立树的过程，其实就和字典树差不多，上面的板子是在叶子处存值，但实际也会有各种存法（比如每个点都存），例如下面这题

（吐槽：太久没用数组建过树了，忘记怎么建了）

题（暴毙）

2021“MINIEYE杯”中国大学生算法设计超级联赛（1）-6：XOR sum

题意

给一个整数数组，你需要找到最短的区间，其按位异或和不小于. 如果有多个，找出左端点最左的

题解

异或运算里，任意x的逆元是本身，故对于前缀和pre[i]和pre[j],i到j的异或和可以表示为pre[i]^pre[j]

这亚子我们去求一个子串的异或和就简单灰常多啦

我们考虑字典树去维护前缀异或和，由于是要求左右端点，所以我们每往字典树中新增一个值，则查找前面的有没有适合的

那这时我们先考虑一个问题。显然一个前缀异或和可能对应好多个前缀子串，那这棵树该存些什么？

因为是边存边处理，然后要尽可能短的子串，所以在相同前缀异或和的情况下，我们存最右边的那个的下标

好了，那如何保证pre[i]^pre[j]>=k?

显然当k的某位为1时，树只能往相异的方向走；为0时则要考虑相异方向的值和同向子树的最大。那我们在每个节点都存最右的值，即可在读到0的时候停下读标号即可

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int p[4000010][2]={0},val[4000010]={0},a[100010]={0};
//记录树的左右分叉（节点下标），树的节点值（最右下标 ），前缀异或和 
int main(){
	int t;
	scanf("%d", &t);
	while(t--){
		int n,k;
		scanf("%d %d", &n,&k);
		for(int i=1;i<=n;i++){
			scanf("%d", &a[i]);
			a[i] ^= a[i-1]; 
		}
		int l=-1,r=n,num=1;//记录答案左端点、右端点、数的节点数 
		val[1]=-1;
		p[1][0] = p[1][1] = 0;//初始化树根
		for(int i=0;i<=n;i++){//从0开始: a[i] = a[i]^0
			int nowl=-1;//记录以i为右当前查到的合适左位置
			int x=1;//记录走到的节点标号 
			for(int j=29;j>=0;j--){
				int abit = (a[i]>>j)&1; //记录a[i]第j位；
				if((k>>j)&1)//如果k的第j位是1，那只能走abit的相反方向
					x = p[x][abit^1];
				else{ //如果k的第j位为0则要考虑abit的相反方向和同方向下一层的最大
					if(p[x][abit^1])
						nowl = max(nowl, val[p[x][abit^1]]);
					x = p[x][abit]; 
				}
				if(!x)break;//如果找不到路，则弹出 
			}
			if(x)
				nowl = max(nowl, val[x]);//如果成功走到最底层也要做一次取最大
			
			//更新l,r
			if(nowl > -1 && i-nowl < r-l)
				l = nowl, r = i;
			
			//将a[i]加入字典树中
			x=1;
			for(int j=29;j>=0;j--){
				int abit = (a[i]>>j)&1;
				if(!p[x][abit]){//如果不存在节点就新建
					p[x][abit] = ++num;
					p[num][0] = p[num][1] = 0;
				}
				x = p[x][abit];
				val[x] = i;//这里不用比较，i肯定比前面的大，直接覆盖就行； 
			}
		}
		if(l>-1)printf("%d %d\n", l+1,r);
		else printf("-1\n");
	} 
	return 0;
}

杭电多校2的第4题貌似也是字典树，但我还没搞懂怎么弄，先鸽着。。。

2021“MINIEYE杯”中国大学生算法设计超级联赛（2）-4：I love counting