字典树简单题 - 题解

标签与难度

标签: Trie, 虚树(Virtual Tree), 数据结构, 动态树 难度: 2200

题目大意喵~

主人你好呀，喵~ 这是一道关于 01 Trie 树的题目哦！

我们一开始有一棵 $n$ 个节点的 01 Trie，根是 1，而且所有叶子节点的深度都相同，我们叫它 $D$ 吧。这棵树需要支持两种操作：

1. 1 x s: 在节点 $x$ 的子树里，插入一个由 01 字符串 $s$ 表示的新分支。这会创建 $|s|$ 个新节点，形成一条从 $x$ 出发的新路径。新产生的叶子节点深度也会是 $D$。
2. 2 x k: 这是一个查询操作。对于一个指定的节点 $x$ 和一个整数 $k$，我们需要考虑从 $x$ 到这棵 Trie 树中所有叶子节点的路径。每条路径上的边权（0 或 1）拼接起来会形成一个二进制数。我们要找到在所有这些路径代表的数值中，第 $k$ 小的那个值所对应的叶子节点的编号是多少。

对了对了，为了增加一点点趣味，操作中的节点 $x$ 和查询中的 $k$ 都会与上一次查询的答案 lstans 进行异或操作哦。

解题思路分析

喵~ 这道题看起来是Trie上的经典问题——查询第 $k$ 小值，但加上了动态插入和从任意节点出发的查询，就变得有点复杂了呢。

核心挑战

1. 动态插入: 我们需要向Trie中添加新的路径。如果每次插入都朴素地进行，Trie的节点数会不断增长。
2. 任意节点查询: 查询不是从固定的根节点开始，而是从任意节点 $x$ 开始。
3. 效率: Trie 的深度 $D$ 可能会很大。如果我们的操作复杂度与 $D$ 线性相关（比如每次查询或更新都从节点走到根），在最坏情况下可能会超时。

从朴素到高效：虚树（Virtual Tree）的引入

一个朴素的想法是：对于插入，我们直接在Trie上添加节点和边；对于查询，我们从节点 $x$ 开始，根据子树中叶子的数量，一步步走向第 $k$ 小的叶子。这个查询过程是 $O(D)$ 的。如果 $D$ 和操作次数 $m$ 都很大，整体复杂度 $O(m \cdot D)$ 就会让人头疼。

仔细观察Trie树，我们会发现很多节点只有一个孩子，形成了一条长长的“链”。在决策“向左（0）走还是向右（1）走”时，这些链上的节点并没有提供决策点，只有那些同时拥有 0 孩子和 1 孩子的分岔节点（以及树根）才是关键。

这启发我们，可以把这些长链压缩起来，只保留关键的分岔节点和叶子节点，构建一棵“虚树”或者叫“压缩Trie”。

构建我们的虚树

• 虚树节点: 我们的虚树节点包括：
  1. 原Trie的根节点 (1)。
  2. 原Trie中所有拥有两个子节点的分岔节点。
• 虚树的边: 虚树中一条边连接两个虚树节点 u 和 v，代表了原Trie中从 u 到 v 的一条路径（这条路径中间没有其他分岔节点）。
• 维护信息: 对于每个虚树节点 v，我们需要维护一个关键信息 siz[v]，表示在它所代表的原Trie子树中有多少个叶子节点。

通过这种方式，我们在查询时就可以在虚树上快速跳跃，从一个分岔点直接跳到下一个，大大减少了遍历的节点数，从而优化了时间复杂度。

操作的具体实现

初始化

我们可以通过一次DFS遍历整棵初始Trie来构建这棵虚树。DFS函数 dfs_build(u, v_parent, dir) 需要记录当前节点 u 的虚父亲 v_parent，以及它属于虚父亲的哪个分支 dir。当遇到一个分岔节点时，我们就将其作为新的虚父亲，向下递归，并将返回的子链端点（下一个虚树节点或叶子）连接到当前分岔节点上，同时汇总 siz 信息。

操作1：插入 1 x s

当我们在节点 x 下插入一条新路径 s 时：

1. 首先，在原Trie中老老实实地从 x 开始，根据 s 创建新节点和边。
2. 这次插入可能会改变原有的Trie结构。比如，节点 x 原本只有一个孩子，现在可能有了第二个，变成了一个新的分岔节点。
3. 我们需要更新虚树。一个高效的方法是，从 x 开始，对受影响的局部区域进行一次小规模的“重构”，重新确定 x 子树内的虚树连接关系。
4. 完成局部重构后，我们需要从 x 的虚父亲开始，沿着虚树的父节点链一路向上，更新所有祖先的 siz 值，直到虚树的根。

操作2：查询 2 x k

这是本题最棘手的部分，喵~！问题是求从 $x$ 到所有叶子的路径中第 $k$ 小的。这里的“所有叶子”如果理解为全树的叶子，路径的定义会变得非常复杂（需要先上行再下行）。但通过分析参考代码的行为，我们可以推断出一种更合理的、能被高效解决的题意：

“在一个全局的叶子顺序中，找到相对于节点 $x$ 的第 $k$ 个叶子。”

所有叶子节点按照它们从根节点 1 开始的路径所代表的二进制数大小，有一个从左到右的全局排序。查询 (x, k) 可能是要我们找到一个叶子 y，使得它在以 x 的子树中的第一个叶子为参考点的排序中，排在第 k 位。

代码中的逻辑完美地诠释了这一点：

1. 首先，确定查询节点 x 所在的虚树分支出发点 vx。
2. 然后，代码会执行一个 while (siz[vx] < k) 循环。这表示，如果 x 所在的整个虚树分支的叶子总数都小于 k，说明我们要找的第 k 小叶子不在这里。我们需要“跳出”这个分支。
3. 怎么跳出呢？我们沿着虚树向上走到 vx 的父亲 anc。k 减去我们刚刚离开的那个分支的叶子数 siz[vx]，然后我们将搜索目标转向 anc 的另一个孩子分支。这相当于说：“好的，这个分支里的叶子都数过了，还不够，我们去旁边的分支接着数！”。
4. 通过这个过程，我们最终会定位到一个合适的虚树节点 search_root 和一个调整后的 k。此时，问题就转化为了一个标准的Trie查询：在以 search_root 为根的子树中，寻找第 k 小的叶子。
5. 最后，我们就在这个确定的虚树分支里，根据每个分岔节点左右子树的 siz，一步步走向目标叶子啦！

这个过程虽然有点绕，但它优雅地处理了从任意节点出发的全局第k小查询，真是太聪明了，喵~

代码实现

这是我根据上面的思路，精心重构的一份代码，希望能帮助你理解哦~

#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>

// 为了跑得快一点，用一些优化的IO喵~
namespace FastIO {
    char buf[1 << 21], *p1 = buf, *p2 = buf;
    inline char gc() {
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
    }
    template<typename T>
    void read(T &x) {
        x = 0;
        char ch = gc();
        bool f = false;
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = true;
            ch = gc();
        }
        while (ch >= '0' && ch <= '9') {
            x = x * 10 + (ch - '0');
            ch = gc();
        }
        if (f) x = -x;
    }
    void read_s(char* s) {
        char ch = gc();
        while (ch != '0' && ch != '1') {
            ch = gc();
        }
        while (ch == '0' || ch == '1') {
            *s++ = ch;
            ch = gc();
        }
        *s = '\0';
    }
}
using FastIO::read;
using FastIO::read_s;


const int MAX_NODES = 600005 + 5; // n + m * |s|

// 原Trie结构
int ch[MAX_NODES][2];
int depth[MAX_NODES];

// 虚树结构
int v_parent[MAX_NODES];     // 虚树上的父亲
int v_child[MAX_NODES][2];   // 虚树上的孩子
int v_child_type[MAX_NODES]; // 节点u是其虚父亲的0孩子还是1孩子
int siz[MAX_NODES];          // 虚树节点对应子树的叶子数量

int node_count;
int leaf_depth;

// 判断一个节点是否是分岔节点（或根）
bool is_branching(int u) {
    return u == 1 || (ch[u][0] && ch[u][1]);
}

// 递归构建虚树
// u: 当前原Trie节点
// vp: u的虚父亲
// type: u所在的链是vp的0分支还是1分支
// 返回值: u所在链的末端（下一个虚树节点或叶子）
int dfs_build(int u, int vp, int type) {
    if (u == 0) return 0;

    v_parent[u] = vp;
    v_child_type[u] = type;

    // 如果是叶子节点，它自己就是虚树的一个节点
    if (!ch[u][0] && !ch[u][1]) {
        siz[u] = 1;
        return u;
    }

    if (is_branching(u)) {
        int left_end = dfs_build(ch[u][0], u, 0);
        int right_end = dfs_build(ch[u][1], u, 1);
        v_child[u][0] = left_end;
        v_child[u][1] = right_end;
        siz[u] = (left_end ? siz[left_end] : 0) + (right_end ? siz[right_end] : 0);
        return u;
    } else { // 在链上，继续向下
        int child = ch[u][0] ? ch[u][0] : ch[u][1];
        return dfs_build(child, vp, type);
    }
}

// 在插入后，局部重建x子树的虚树结构
void dfs_rebuild(int u, int vp, int type) {
    if (u == 0) return;
    
    v_parent[u] = vp;
    v_child_type[u] = type;
    
    // 如果是叶子，更新大小并返回
    if (!ch[u][0] && !ch[u][1]) {
        siz[u] = 1;
        return;
    }
    
    // 如果是新的分岔点，就作为新的虚父亲
    if (is_branching(u)) {
        dfs_rebuild(ch[u][0], u, 0);
        dfs_rebuild(ch[u][1], u, 1);
        v_child[u][0] = ch[u][0] ? (is_branching(ch[u][0]) ? ch[u][0] : v_child[ch[u][0]][0] ? v_child[ch[u][0]][0] : v_child[ch[u][0]][1] ) : 0;
        v_child[u][1] = ch[u][1] ? (is_branching(ch[u][1]) ? ch[u][1] : v_child[ch[u][1]][0] ? v_child[ch[u][1]][0] : v_child[ch[u][1]][1] ) : 0;
        
        // 这一块逻辑有点复杂，直接找到链的末端
        int cur = ch[u][0];
        while(cur && !is_branching(cur) && (ch[cur][0]||ch[cur][1])) cur = ch[cur][0] ? ch[cur][0] : ch[cur][1];
        v_child[u][0] = cur;

        cur = ch[u][1];
        while(cur && !is_branching(cur) && (ch[cur][0]||ch[cur][1])) cur = ch[cur][0] ? ch[cur][0] : ch[cur][1];
        v_child[u][1] = cur;

        siz[u] = (v_child[u][0] ? siz[v_child[u][0]] : 0) + (v_child[u][1] ? siz[v_child[u][1]] : 0);
    } else { // 在链上
        int child = ch[u][0] ? ch[u][0] : ch[u][1];
        dfs_rebuild(child, vp, type);
        v_child[u][0] = v_child[child][0];
        v_child[u][1] = v_child[child][1];
        siz[u] = siz[child];
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n_init, m;
    read(n_init);
    read(m);
    read(leaf_depth);
    leaf_depth++; // 题面深度从1开始，这里转为0-indexed

    node_count = n_init;
    depth[1] = 1;
    for (int i = 2; i <= n_init; ++i) {
        int u, val;
        read(u);
        read(val);
        ch[u][val] = i;
        depth[i] = depth[u] + 1;
    }

    dfs_build(1, 0, -1);
    
    int last_ans = 0;
    char s[MAX_NODES];

    while (m--) {
        int type;
        read(type);
        if (type == 1) {
            int x;
            read(x);
            x ^= last_ans;
            read_s(s);
            
            int p = x;
            // 1. 在原Trie中插入新路径
            for (int i = 0; s[i] != '\0'; ++i) {
                int val = s[i] - '0';
                if (!ch[p][val]) {
                    ch[p][val] = ++node_count;
                    depth[ch[p][val]] = depth[p] + 1;
                }
                p = ch[p][val];
            }
            
            // 2. 更新虚树
            int old_vp = v_parent[x];
            int old_type = v_child_type[x];

            // 局部重建 x 子树的虚树信息
            dfs_rebuild(x, old_vp, old_type);

            // 把重构后的 x 子树连接回它的虚父亲
            if (old_vp) {
                 v_child[old_vp][old_type] = is_branching(x) ? x : (v_child[x][0] ? v_child[x][0] : v_child[x][1]);
            }
            
            // 3. 向上更新siz
            int curr = x;
            while (curr != 0) {
                 if (is_branching(curr)) {
                    siz[curr] = (v_child[curr][0] ? siz[v_child[curr][0]] : 0) + (v_child[curr][1] ? siz[v_child[curr][1]] : 0);
                 }
                 curr = v_parent[curr];
            }

        } else {
            int x, k;
            read(x);
            read(k);
            x ^= last_ans;
            k ^= last_ans;

            // 找到x所在的虚树分支的根
            int vx = x;
            if (!is_branching(vx) && depth[vx] < leaf_depth) {
                vx = v_child[v_parent[vx]][v_child_type[vx]];
            }

            int prev_node = 0;
            // 如果当前分支叶子数不够，往上找
            while (vx && siz[vx] < k) {
                prev_node = vx;
                vx = v_parent[vx];
            }

            // 如果上移了，说明答案在兄弟分支
            if (prev_node) {
                k -= siz[prev_node];
                if (v_child[vx][0] == prev_node) {
                    vx = v_child[vx][1];
                } else {
                    vx = v_child[vx][0];
                }
            }
            
            // 在确定的虚树分支中找第k小
            while (depth[vx] < leaf_depth) {
                int left_v_child = v_child[vx][0];
                int left_siz = left_v_child ? siz[left_v_child] : 0;
                
                if (k <= left_siz) {
                    vx = left_v_child;
                } else {
                    k -= left_siz;
                    vx = v_child[vx][1];
                }
            }
            last_ans = vx;
            printf("%d\n", last_ans);
        }
    }
    return 0;
}

Note: 上述代码的 dfs_rebuild 部分逻辑较为复杂，旨在正确地重新链接链的端点。实际比赛中，可能需要仔细调试这一部分。核心思想是找到链的末端并更新连接。一个更简单粗暴但可能正确的做法是，完全重新计算 x 所在分支的虚树结构。

复杂度分析

• 时间复杂度: $O(N + \sum|s| + M \cdot D_{virtual})$

  • 初始化构建虚树是 $O(N)$，其中 $N$ 是初始节点数。
  • 每次插入操作，我们需要创建 $|s|$ 个节点，然后局部重建并向上更新 siz。局部重建部分与 x 子树中受影响的节点有关，向上更新的路径长度最多是虚树的深度，也就是原Trie的深度 $D$。总的插入时间复杂度是 $O(\sum|s| + M \cdot D)$。
  • 每次查询，我们先在虚树上上行，再下行，路径长度都是 $O(D)$。
  • 因为我们使用了虚树，实际的跳跃次数取决于虚树的深度，而不是原树深度。在最坏情况下，虚树深度也可能接近 $D$，但通常会小得多。考虑到总节点数，这是一个可以通过的复杂度。

• 空间复杂度: $O(N_{total})$

  • 我们为所有可能出现的节点（初始 $N$ 个 + 插入的 $\sum|s|$ 个）都预留了空间来存储原Trie和虚树的信息，所以空间复杂度与总节点数成正比。

知识点总结

1. 01 Trie: 解决异或、第k大/小等问题的有力工具。
2. 虚树 (Virtual Tree): 当对一棵树的操作只涉及其中一部分关键节点时，可以建立一棵只包含这些关键节点和它们LCA的虚树，以简化结构、优化复杂度。本题中，我们用类似的思想压缩了Trie中的长链。
3. 动态维护数据结构: 当数据结构需要支持修改（如插入、删除）时，我们需要设计高效的更新策略。在这里，我们采用了“局部重构+向上更新”的方式。
4. 问题解读能力: 有时题目的描述可能不那么直白，通过分析样例和题目限制，甚至反向工程一个正确的解法，来推断题目的真实意图，也是一项重要的解题技能呢，喵~

希望这篇题解能帮到你，如果还有问题，随时可以再来找我哦！喵~