字典树

插入和查询某个单词

cpp实现

const int N = 5e5 + 5;
int son[N][26], cnt[N], idx; // 存树，cnt记录某个节点为结尾的字符串个数
// idx 索引位置，与图论中相似，0 位置是整个树的树根（没有值，就是查询起点），也表示空节点
 
void insert(string str) {
    int p = 0; // 树根
    for (int i = 0; i < str.size(); i++) {
        int t = str[i] - 'a';
        if (!son[p][t]) son[p][t] = ++idx; // 若此节点没有值，给此节点赋值（索引）
        p = son[p][t]; // 在树中向下寻找，相当于进入下一层
    }
    cnt[p]++; // 以此节点为结尾的计数++
}
 
// 查询过程与插入过程相似
int query(string str) {
    int p = 0;
    for (int i = 0; i < str.size(); i++) {
        int t = str[i] - 'a';
        if (!son[p][t]) return 0; // 查找不到，说明没有，返回 0
        p = son[p][t];
    }
    return cnt[p]; // 返回单词出现的次数
}

01字典树

一般用于求异或最大值

const int N = 5e5 + 5;
int son[32 * N][2], idx = 1, val[32 * N]; // val表示到该节点的值

// 初始化
void init()
{
    idx = 1;
    son[0][0] = son[0][1] = 0;
}

void insert(int n)
{
    int p = 0;
    for(int i = 31; i >= 0; i--) {
        int t = 1 & (n >> i);
        if(!son[p][t]) {
            son[idx][0] = son[idx][1] = 0;
            val[idx] = 0; // 初始化新节点
            son[p][t] = idx++;
        }
        p = son[p][t];
    }
    val[p] = n;
}

int query(int n)
{
    int p = 0;
    for(int i = 31; i >= 0; i--) {
        int t = !(1 & (n >> i));
        if(son[p][t] == 0) {
            t = !t;
        }
        p = son[p][t];
    }
    return val[p] ^ n; // 返回异或后的最大值
}

任意区间异或最大值

设 为前 项的前缀异或和, 为前 项中任意区间异或的最大值，则可以通过以下方式求出

init();
insert(pre[0]);
for(i=1;i<=n;i++)
{
    dp[i]=max(dp[i-1],query(pre[i]));
    insert(pre[i]);
}

最长异或路径

异或路径指的是指树中两个节点之间唯一路径上的所有边权的异或。

ll ans;

void dfs(int u, int f, ll val)
{
    insert(val);
    for(auto [v, w] : g[u]) {
        if(v == f)  continue;
        ans = max(ans, query(val ^ w));
        dfs(v, u, val ^ w);
    }
}

dfs(1, -1, 0);

dfs过程中未取消点的访问，如何确保连续? 考虑三种情况:

1. 深搜的两条路径一个包含在另一个中，这样一异或，公共的部分的值变成 了，剩下的部分是连续的。
2. 深搜的两条路径部分重叠，同理，异或后公共的部分变成 了，由于是对边权的异或，剩下的部分仍然连续。
3. 深搜的两条路径不重叠，但是两条路径肯定有公共的点——根节点，也是连续的。