Trie树

用于高效地存储和查找字符串集合的数据结构。

一般用到trie树的地方，字符串：要么全是小写字母、要么全是大写字母、要么是数字（0、1）.....

总之字符的数量不会很多。

创建trie树的过程：

如果有一系列字符串："abcdef", "abdef", "aced", "bcdf".....

设置一个根节点，我们以"abcdef"为例，从根节点开始，遍历根节点的子节点，查找里面是否有"a"，如果没有就创建一个，如果有就找到这个节点；然后继续查找"a"节点的根节点有没有"b"，如果没有就创建一个，如果有就找到这个节点....直到遍历完整个字符串，然后在最后一个节点上打一个标记，表示这个地方是某一个单词的结尾。

那么trie数有什么用呢？

它可以高效的查找某个字符串是否出现过以及出现过多少次。

AcWing 835. Trie字符串统计

#include using namespace std;const int N = 100010;
// idx表示下标，根节点和空节点的下标均为0；cnt[N]数组用于存放终点字符的数量
// son[N][26]表示每个节点最多可能有26个根节点
int son[N][26], cnt[N], idx, n;
char str[N];void insert(char str[]){int p = 0;// 遍历字符串for(int i = 0; str[i]; i++){int u = str[i] - 'a';if(!son[p][u]) son[p][u] = ++idx;p = son[p][u];}cnt[p]++;
}int quiry(char str[]){int p = 0;for(int i = 0; str[i]; i++){int u = str[i] - 'a';if(!son[p][u]) return 0;p = son[p][u];}return cnt[p];
}int main(){scanf("%d", &n);while(n--){char op[2];scanf("%s %s", op, str);if(op[0] == 'I') insert(str);else printf("%d\n", quiry(str));}return 0;
}

AcWing 143. 最大异或对

暴力

#include using namespace std;const int N = 100010;
int a[N];
int res, n;int main(){scanf("%d", &n);for(int i = 0; i < n; i++){scanf("%d", &a[i]);}for(int i = 0; i < n; i++){for(int j = 0; j < i; j++){res = max(res, a[i] ^ a[j]);}}printf("%d", res);
}

毫无疑问超时，需要优化至O(nlogn)。

内层循环是在固定a[i]后，从a[0]到a[i-1]中找到一个与a[i]异或值最大的一个数。

再来看本题的数据范围，每一个数都是小于2^31，所以都可以看成一个长度为31位的二进制串。

现在假设我们有一个长度为31的二进制串：

111011100......1
|<----31------>|
要想找到异或的最大值，那么最高位越大则越大，所以a[j]最高位为0所得的异或的值一定比最高位为1的异或的值要大
于是我们就只关心最高位为0的a[j]值，然后以此类推再找第二高位为[0]的a[j]值....
这样就完成了剪枝优化操作（贪心）
在trie中每次都向与a[i]字符串字符不同的分支上走即可

于是现在时间复杂度就从10^5 * 10^5 ---> 31 * 10^5

#include using namespace std;const int N = 100010, M = 31 * N;
int a[N];
int n, son[M][2], idx;void insert(int x){int p = 0;for(int i = 30; i >= 0; i--){int u = x >> i & 1;if(!son[p][u]) son[p][u] = ++idx;p = son[p][u];}
}int quiry(int x){int p = 0, res = 0;for(int i = 30; i >= 0; i--){int u = x >> i & 1;if(son[p][!u]){p = son[p][!u];res = res * 2 + !u;} else{p = son[p][u];res = res * 2 + u;}}return res;
}int main(){scanf("%d", &n);for(int i = 0; i < n; i++){scanf("%d", &a[i]);}int res = 0;for(int i = 0; i < n; i++){insert(a[i]);int t = quiry(a[i]);res = max(res, a[i] ^ t);}printf("%d\n", res);return 0;
}

AcWing 3485. 最大异或和

要求子数组的异或和，即为子数组中所有元素按位异或得到的结果。

异或的重要性质：

s = a ^ b ---> a = s ^ b;
有一个数组：
|___________|_________|________|
0           L         R        n
要求L到R的元素的异或和，那么只需求：
从第0个元素到第L-1个元素的异或和s_L-1 = a1 ^ a2 ^ ... ^ aL-1
从第0个元素到第R个元素的异或和s_R = a1 ^ a2 ^ ... ^ aR
则从L到R的元素的异或和sum = s_L-1 ^ s_R
相当于从1 - L-1异或一遍，再从1 - R异或一遍，同一个数异或两次就抵消了：0^0=0, 1^1=0
所以从0 - L-1的数就全为零，得到的sum值即为从L-R的异或和

于是本题相当于维护一个滑动窗口内的trie树，引入一个变量来记录每个节点的数量，每次添加元素时就当前路径上所有节点数量加一，每次删除元素时就当前路径上所有节点数量减一，最少为0。

#include using namespace std;const int N = 100010 * 31;
int son[N][2], cnt[N], idx;
int n, m, s[N];void insert(int x, int v){int p = 0;for(int i = 30; i >= 0; i--){int u = x >> i & 1;if(!son[p][u]) son[p][u] = ++idx;p = son[p][u];cnt[p] += v;}
}int quiry(int x){int res = 0, p = 0;for(int i = 30; i >=0; i--){int u = x >> i & 1;if(cnt[son[p][!u]]){p = son[p][!u];res = 2 * res + 1;}else{p = son[p][u];res = 2 * res;}}return res;
}int main(){scanf("%d %d", &n, &m);for(int i = 1; i <= n; i++){int x;scanf("%d", &x);s[i] = s[i - 1] ^ x;}int res = 0;insert(s[0], 1);for(int i = 1; i <= n; i++){if(i - m - 1 >= 0)insert(s[i - m - 1], -1);res = max(res, quiry(s[i]));insert(s[i], 1);}printf("%d\n", res);return 0;
}