字典树本质是将多个字符串的$26$个分支或多个数字的每个二进制位的$01$情况反映到一棵树上，然后针对分支情况进行讨论选择

一、$Acwing143$-最大异或对

本题即将给定所有数的数位$01$情况反映到一棵树中，然后枚举每个数$x$，讨论其他数的数位能和$x$的当前位异或产生的最大值

二、$lc1803$-满足异或对条件的数的数目

本题中求满足满足异或值在$[left,\ right]$的所有所有数对个数，由前缀和性质：求出两两异或值小于$right+1$的数对个数，减去两两异或值小于$left$的数对个数，即异或值在$[left,\ right]$的所有所有数对个数

那么相当于将所有数的数位状态都反映到$trie$树中，根据上限$limit$每位的情况，为每个$x$在$trie$树中选择满足条件的数位

本题中的满足条件的数位即如果上限$limit$当前位为$1$，那么假设当前枚举的$x=nums[i]$的这一位为$v$，那么$trie$树中为它选择的数位应该和$v$一样，这样$x$当前位和选择的分支位亦或值为$0$，那么以当前$son[p][v]$点为中间数位的所有数都满足异或值小于$limit$的限制，可以一起统计

为了实现一起统计的目的，我们需要在$insert(x)$的时候，对$x$的每一数位所在$cnt[idx]$都$+1$

同时如果在从$trie$树中挑选满足条件的数提前终止($p=0$)，那么说明后面已经没有满足条件的数了，必须立即返回当前计算得到的$ans$，否则$p=0$又会回到根节点重新开始计算导致错误

#include<bits/stdc++.h>
using namespace std;
const int N = 2e4+10;
int son[15 * N][2], cnt[15 * N], idx;
class Solution {
public:
    void insert(int x)
    {
        int p = 0;
        for (int i = 15; i >= 0; i --)
        {
            int u = x >> i & 1;
            if (!son[p][u]) son[p][u] = ++ idx;
            p = son[p][u];
            cnt[p] ++;  // 为了实现通过一个结点统计后面一共有多少数，每一个结点都要+1
        }
    }
    int search(int x, int limit)
    {
        int p = 0, ans = 0;
        for (int i = 15; i >= 0; i --)
        {
            int v = x >> i & 1;  // 获取x当前位
            if (limit >> i & 1)  // 如果limit当前位是1，那么当前数位选和x当前数位的数一样 最终的结果一定小于limit
            {
                if (son[p][v]) ans += cnt[son[p][v]];
                p = son[p][v ^ 1];  // 选择与x的当前位相反的数，当前位异或获得的值为1
            }
            else p = son[p][v];  // 如果limit当前位是0，这一位就只能选和x这一位相同的来获得异或结果0，否则异或的结果会大于limit
            if (!p) return ans;  // 如果当前已经没有儿子了，那么必须立即停止，否则又会从根节点开始错误的继续选择
        }
        return ans;
    }
    void init()
    {
        idx = 0;
        memset(cnt, 0, sizeof cnt);
        memset(son, 0, sizeof son);
    }

    int countPairs(vector<int>& nums, int low, int high) {
        init();
        int ans = 0;
        for (auto t : nums) insert(t);
        for (auto t : nums) ans += search(t, high + 1) - search(t, low);
        return ans / 2;  // nums[i]算了nums[j]，nums[j]又算了nums[i]重复计算要÷2
    }
};

三、$Acwing835$-$Trie$字符串统计

本题为将所有字符串的$26$个字母分支反映到$trie$树中，在每个字符串结尾进行计数，然后统计某个字符串出现的次数，即只需按照要查询的字符串选择分支到结尾即可得到出现次数