写在前面
字典树(TireTree)，典型应用是用于统计，排序和保存大量的串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。(取自百度百科) 类似于字符串，在以位作为公共前缀的整形数操作中，也是可以使用的，本模板中的例子就是整形数作为字典树前缀的，普通字符串的字典树较容易理解，就不在记录模板了。
代码模板
由于字典树单独写成板子并不容易理解，故此处使用一道题目的代码来展示字典树板子，使用数组模拟(直接使用树结构也可)，其中idx表示结点的编号，son[i][0]表示结点i的第0个孩子（即下一位数字是0），son[i][1]同理。题目链接： 1707 - 与数组中元素的最大异或值
class Solution {
int[][] son;
int idx = 0;
public void add(int num){
//当前结点
int cur = 0;
for(int i = 30; i >= 0; i--){
int u = (num >> i) & 1;
if(son[cur][u] == 0){
son[cur][u] = ++idx;
}
cur = son[cur][u];
}
}
public int query(int num){
if(idx == 0) return -1;
int res = 0;
int cur = 0;
for(int i = 30; i >= 0; i--){
int u = (num >> i) & 1;
if(son[cur][u ^ 1] != 0){
//可以走相反方向
res = res * 2 + 1;
cur = son[cur][u ^ 1];
}else{
res = res * 2;
cur = son[cur][u];
}
}
return res;
}
public int[] maximizeXor(int[] nums, int[][] queries) {
int n = queries.length;
son = new int[n * 31][2];
Integer[] idxs = new Integer[n];
for(int i = 0; i < n; i++) idxs[i] = i;
//排序
Arrays.sort(nums);
Arrays.sort(idxs, (i1, i2) -> queries[i1][1] - queries[i2][1]);
int[] res = new int[n];
int j = 0;
for(int i = 0; i < n; i++){
int idx = idxs[i];
int x = queries[idx][0], m = queries[idx][1];
while(j < nums.length && nums[j] <= m){
add(nums[j++]);
}
res[idx] = j == 0 ? -1 : Math.max(res[idx], query(x));
}
return res;
}
}
主要需要思考的地方就是query方法内部返回的结果，这道题由于是异或运算，选择不同的位对应结果更大，没有不同的位便只能走相同的位，最后找到最大的异或值即可。
补充 - 233场周赛第4题
这也是一道整形作前缀的字典树的问题，题目链接为：5696. 统计异或值在范围内的数对有多少
这道题补充一下使用树结构模拟字典树的方法，较数组模拟来说比较简单。
代码模板01 - 数组模拟字典树
class Solution {
int[] nums;
//trie
int[][] son = new int[20005 * 15][2];
int[] cnt = new int[20005 * 15];
int idx = 0;
public void insert(int num){
int root = 0;
for(int i = 15; i >= 0; i--){
int a = num >> i & 1;
if(son[root][a] == 0) son[root][a] = ++idx;
root = son[root][a];
cnt[root]++;
}
}
//返回与x的异或值小于high的漂亮数对数
public int query(int x, int high){
int root = 0;
int res = 0;
for(int i = 15; i >= 0; i--){
int a = x >> i & 1, b = high >> i & 1;
if(b == 1){
res += cnt[son[root][a]];
root = son[root][a ^ 1];
}else
root = son[root][a];
if(root == 0) break;
}
return res;
}
public int countPairs(int[] nums, int low, int high) {
this.nums = nums;
int res = 0;
//将所有数存入字典树中
for(int num : nums) insert(num);
for(int num : nums){
res += query(num, high + 1) - query(num, low);
}
return res / 2;
}
}
代码模板02 - 树结构模拟字典树
class Solution {
int[] nums;
//trie
Node node = new Node();
public void insert(int num){
Node root = node;
for(int i = 15; i >= 0; i--){
int a = num >> i & 1;
if(root.sons[a] == null) root.sons[a] = new Node();
root = root.sons[a];
root.cnt++;
}
}
//返回与x的异或值小于high的漂亮数对数
public int query(int x, int high){
Node root = node;
int res = 0;
for(int i = 15; i >= 0; i--){
int a = x >> i & 1, b = high >> i & 1;
if(b == 1){
res += root.sons[a] == null ? 0 : root.sons[a].cnt;
root = root.sons[a ^ 1];
}else
root = root.sons[a];
if(root == null) break;
}
return res;
}
public int countPairs(int[] nums, int low, int high) {
this.nums = nums;
int res = 0;
//将所有数存入字典树中
for(int num : nums) insert(num);
for(int num : nums){
res += query(num, high + 1) - query(num, low);
}
return res / 2;
}
}
class Node{
Node[] sons;
int cnt;//cnt存储当前结点所有直接或间接孩子的数目，，用于最终答案统计
public Node(){
sons = new Node[2];
cnt = 0;
}
}
这道题用到了统计数目的cnt，需要注意cnt定义为：存储当前结点所有直接或间接孩子的数目，，用于最终答案统计。
其次，根据容斥原理，可以将所求的区间转换为两个同号的区间，即[low, high] -> [0, high+1) - [0, low)，这样在查询的时候根据位运算的性质统计答案即可。
