你好！作为金牌教练，我发现你现在开始接触字符串高级数据结构了。LeetCode 的“实现 Trie (前缀树)”是学习字符串处理的入门基石，但在 NOI（信息学奥赛）中，我们通常不使用面向对象的 class 写法，而是采用更高效、更节省内存的静态数组模拟指针的写法。

下面我将这道题按照 NOI 竞赛的规范进行改写，并提供启发式的逻辑引导。

题目名称：Implement Trie (前缀树)

题目描述

前缀树（Trie）是一种用于快速检索字符串数据集中的键的树形数据结构。在信息学奥赛中，它常用于统计、排序和保存大量的字符串。

请你实现一个能够完成以下三个功能的 Trie 树：

1. insert(word): 向 Trie 中插入字符串 word。
2. search(word): 如果字符串 word 在 Trie 中，返回 true；否则返回 false。
3. startsWith(prefix): 如果 Trie 中有一个字符串以 prefix 为前缀，返回 true；否则返回 false。

输入格式

第一行包含一个整数 $Q$，表示操作的总次数。 接下来的 $Q$ 行，每行首先包含一个操作命令字符串（Trie, insert, search, startsWith 中的一种）。 如果是 insert, search, startsWith 命令，其后会紧跟一个空格和一个操作字符串。 注：Trie 命令仅用于初始化，不带参数。

输出格式

对于每一个操作，输出一行。

• Trie、insert 操作输出 null。
• search、startsWith 操作输出 true 或 false。

样例数据

输入：

7
Trie
insert apple
search apple
search app
startsWith app
insert app
search app

输出：

null
null
true
false
true
null
true

数据规模说明

• $1 \le Q \le 5 \times 10^4$
• 插入及查询的字符串总长度不超过 $10^5$。
• 字符串仅由小写英文字母组成。
• 在 NOI 比赛中，请注意内存限制，建议使用静态数组实现。

预备知识点

1. 字符映射：将字符 'a'-'z' 映射为数字 0-25。
2. 二维数组模拟树结构：trie[idx][26] 表示编号为 idx 的节点在接收某个字符后指向的下一个节点编号。
3. 标记位：isEnd[idx] 布尔数组，记录该编号对应的节点是否是一个单词的结尾。

启发式思路引导（草稿纸推理过程）

想象你在一张空白草稿纸上：

1. 节点 0 是根节点。它不代表任何字符，只是所有单词的起点。
2. 插入 "apple"：
   • 从根节点出发，看有没有通往 'a' 的路？没有，就建一个新房间（给它一个编号 1）。
   • 进入房间 1，看有没有通往 'p' 的路？没有，建房间 2。
   • ...直到最后一个字母 'e' 所在的房间，打上一个“单词结束”的红旗。
3. 查询 "app"：
   • 沿着 'a'->'p'->'p' 走。如果路断了，直接判定为 false。
   • 如果走到了最后一个 'p' 的房间：
     • search 操作：看这间房有没有红旗？没有，返回 false。
     • startsWith 操作：只要能走到这间房，说明有单词以此为前缀，返回 true。

核心逻辑流程图（伪代码提示）

在 NOI C++ 编程中，我们通常定义全局数组 int trie[MAXN][26] 和 bool is_end[MAXN]。

1. 插入操作 (Insert)

graph TD
    A("开始: insert word") --> B("初始化 p = 0 (根节点)")
    B --> C{"遍历 word 中的每个字符 c"}
    C -- "还有字符" --> D("计算编号 id = c - 'a'")
    D --> E{"trie[p][id] 是否为 0 ?"}
    E -- "是 (无路)" --> F("trie[p][id] = ++tot (新建节点)")
    F --> G("p = trie[p][id] (进入下一层)")
    E -- "否 (有路)" --> G
    G --> C
    C -- "字符遍历完" --> H("标记 is_end[p] = true")
    H --> I("结束")

2. 检索操作 (Search / StartsWith)

graph TD
    A("开始: search/startsWith s") --> B("初始化 p = 0")
    B --> C{"遍历 s 中的每个字符 c"}
    C -- "还有字符" --> D("计算编号 id = c - 'a'")
    D --> E{"trie[p][id] == 0 ?"}
    E -- "是 (路径中断)" --> F("返回 false")
    E -- "否 (继续)" --> G("p = trie[p][id]")
    G --> C
    C -- "字符遍历完" --> H{"判断操作类型"}
    H -- "是 search" --> I("返回 is_end[p]")
    H -- "是 startsWith" --> J("返回 true")

复杂度分析与优化建议

1. 时间复杂度：
   • 插入和查询均为 $O(L)$，其中 $L$ 是当前字符串的长度。
   • 与 Trie 中存储了多少单词无关，这使得它在处理大量字符串时极快。
2. 空间复杂度分析：
   • 空间复杂度为 $O(N \times \Sigma)$，其中 $N$ 是所有单词不同前缀的总个数，$\Sigma$ 是字符集大小（此处为 26）。
   • NOI 提示：如果内存限制极严（例如只有 64MB），而字符串非常离散，静态二维数组可能会爆内存。此时可以考虑使用 std::vector 动态开辟或左孩子右兄弟表示法，但在大多数 NOI 题目中，合理分配 MAXN 即可。
3. 读题关键词：
   • “前缀”、“字符串集合”、“出现次数统计”。
   • 注意：如果题目涉及大写字母、数字或特殊符号，需要调整 26 这个维度的数值及映射函数。

希望这个引导能帮你更好地理解前缀树在竞赛中的实现！准备好动手写出你的 int trie[100005][26] 了吗？