字典树

树形结构， 消除冗余，实现结点的共用问题

本质上是一颗多叉树，$tr[u][i]$，表示当前结点的儿子。

数组模拟链表，邻接表表示的是边的信息。

e[idx], ne[idx] 存是的e[idx]这个结点到e[ne[idx]]这个结点的这条边的信息

字典树也同理

tr[p][u] 存的是他的下一个结点相当于ne[idx], 边的信息由二维数组tr的第二维来存储，idx相当于给下一个结点分配内存池，下一个结点还对应着一些边由tr[tr[p][u]][x]来存

插入操作

• 字符串

void insert(char str[]) {
	int p = 0; // 树形结构，从跟开始遍历
    for (int i = 0; str[i]; i ++) {
		int u = str[i] - 'a';
        if (!tr[p][u]) tr[p][u] = ++idx; // 没有这个子节点就创建一个，否则就直接走过去实现共用
        p = tr[p][u];
    }
	cnt[p] ++; // 表示当前这个点是某个有效信息
}

• 二进制数

void insert(int x) {
	int p = 0;
	for (int i = 30; i >= 0; i --) {
		int u = x >> i & 1; // 判断这一位是0，1
        if (!tr[p][u]) tr[p][u] = ++idx; // 开点或共用
        p = tr[p][u];	
	}
    num[p] ++; // 当前是一个数
}

查询操作

• 字符串出现次数

int query(char *str) {
    // 查询往下递归找即可
    int p = 0;
    for (int i = 0; str[i]; i ++) {
		int u = str[i] - 'a';
        if (!tr[p][u]) return 0; // 结点不存在，即字符串不存在
        p = tr[p][u]; 
    }
    return cnt[p];
}

• 最大异或对

int query(int x) {
	int p = 0, res = 0;
    for (int i = 30; i >= 0; i --) {
		int u = x >> i & 1; // 当前这一位是什么，贪心来看高位能不同就不同可以决定性
        if (tr[p][!u]) res += 1 << i, p = tr[p][!u]; // 如果这一位可以取1那就直接取，否则就只能取零，因为只有两个结点
        else p = tr[p][u];						     // 所以每一个结点的两个子节点至少有一个是有的，因此不会走到空结点
        // 往前缀相同的一些数的下面的位贪心
    }
    return res;
}

清空操作

我们相当于用$idx$来分配的内存池，所以直接

for (int i = 0; i <= idx; i ++) tr[i][j] = 0;
idx = 0;