ch05 课堂参考代码及部分题目思路

ch05 字典树

字典树（Trie）是一种用于实现字符串快速查找的多叉树结构，查找原理类似于我们在英文词典上查找单词。

字典树用边来代表字母，从根结点到树上某一结点的路径就代表了一个字符串。

字典树的表示

• 以字符集为小写字母的字典树为例，是一棵 26 叉树，每个结点都需要记录它的 26 个子结点编号（就像二叉树中用 lc 和 rc 记录左右子结点编号），ch[0] 记录 ‘a’ 这条边对应的子结点编号，ch[1] 记录往 ‘b’ 这条边对应的子结点编号，以此类推。ch[i] = 0 表示还没有这条边（还没有这个子结点）。
• 为了支持词频统计、前缀匹配相关的查找，每个结点还需要记录 cnt 和 siz。cnt 表示从根结点到当前结点的路径所代表的字符串的个数（或者理解为当前结点是 cnt 个字符串的结尾），siz 是子树的 cnt 之和（可以发现这里的 cnt 和 siz 的含义类似“二叉查找树”中的 cnt 和 siz）。
• 初始化：一棵空的字典树仅包含根结点（根结点编号为 0），ch[i] 、cnt、siz 均为 0。

const int maxn = 1000010;
struct Node{int ch[26];int cnt, siz;
} trie[maxn];
int tot; // 已经使用的结点编号 0~tot，下一次新结点编号为 tot+1

插入操作

• 当需要插入一个字符串 s 时，从根结点出发，然后依次扫描 s 中的每个字符 s[i] ，根据 s[i] 这个字符决定往哪个子结点走，子结点不存在时新建结点。同时进行 cnt 和 siz 的修改。

// 往字典树中插入字符串s
void ins(string s) {int u = 0;for (int i = 0; i < s.size(); i++) {int p = s[i] - 'a';if (trie[u].ch[p] == 0) trie[u].ch[p] = ++tot;u = trie[u].ch[p];trie[u].siz++;}trie[u].cnt++;
}

查询操作

1. 查询字符串 s 是否在字典树中

   • 类似插入操作，从根结点往下走，有两个情况说明不存在字符串 s：一是往下走的过程中子结点不存在，走不通；二是走到字符串 s 的结尾结点了，但是该结点的 cnt == 0，说明之前插入的字符串的前缀有 s，但没有插入过字符串 s 。

   bool query1(string s) {int u = 0;for (int i = 0; i < s.size(); i++) {int p = s[i] - 'a';if (trie[u].ch[p] == 0) return false;u = trie[u].ch[p];}return trie[u].cnt > 0;
   }
   

2. 查询有多少个字符串的前缀有 s

   int query2(string s) {int u = 0;for (int i = 0; i < s.size(); i++) {int p = s[i] - 'a';if (trie[u].ch[p] == 0) return 0;u = trie[u].ch[p];}return trie[u].siz;
   }
   

3. 查询有多少个字符串是s的前缀

   int query3(string s) {int u = 0, sum = 0;for (int i = 0; i < s.size(); i++) {int p = s[i] - 'a';if (trie[u].ch[p] == 0) return sum;u = trie[u].ch[p];sum += trie[u].cnt;}return sum;
   }
   

遍历

• 遍历字典树，类似二叉树的遍历，只是改为 26 叉树的遍历

void dfs(int u) {// 当前访问到字典树上编号为u的结点for (int i = 0; i < 26; i++) {int v = trie[u].ch[i]; // u的第i个子结点if (v) dfs(v); // 子结点v存在，往v搜索}
}

复杂度

• 时间复杂度：插入和查询都是遍历字符串，从根结点往下走，所以时间复杂度是 $O(|s|)$ ，$|s|$ 表示字符串 s 的长度。
• 空间复杂度： $O(NC)$ ，其中 N 是结点数量（所有字符串长度之和），C 是字符集大小（仅包含小写字母则 C = 26）。
• 字典树时间复杂度很好，空间复杂度比较差，是一种空间换时间的数据结构。

01 字典树

01 字典树是一种特殊的字典树，字符集只有 0 和 1（二叉树），可以维护整数二进制异或的相关信息。

例题：最大异或查询

• 分析：

  • 题目要查找 x 与另一个数异或之后的最大结果，按照贪心的思路，优先让结果的二进制高位尽量是 1，这样结果最大。
  • 对于要添加的整数 x，将 x 的二进制插入字典树中，从高位往低位插入，这里要考虑 x 的二进制最多有多少位，例如 $10^{18}$ 二进制最多 60 位，那么从第 60 位开始插入（从第 0 位开始数则是第 59 位，这里位数算多一点没有关系，算少了就会错误）。
  • 查询时，从高位往低位，要让当前位的异或结果尽量是 1，那么就要往相反方向搜索，x 这一位是 1，则要往 0 的子结点走，x 这一位是 0，则要往 1 的子结点走，子结点不存在就只能往相同方向搜索。

• 主要代码：

  // 插入数字x的二进制表示（从高位到低位插入）
  void ins01(ll x) {int u = 0;for (int i = 59; i >= 0; i--) {int p = (x >> i) & 1;if (trie[u].ch[p] == 0)trie[u].ch[p] = ++tot;u = trie[u].ch[p];trie[u].siz++;}trie[u].cnt++;
  }
  // 查询与x异或的最大结果
  ll queryMaxXor(ll x) {int u = 0;ll res = 0;for (int i = 59; i >= 0; i--) {int p = (x >> i) & 1;if (trie[u].ch[p ^ 1]) {res |= (1LL << i);u = trie[u].ch[p ^ 1];} elseu = trie[u].ch[p];}return res;
  }
  

ch05 部分题目解法

偏序统计

• 分析：

  • 注意本题不能像“最大异或查询”那道题一样插入数字 x，在异或问题中，需要权重相同的二进制位对齐，所以二进制都前面补 0 使它们长度相同，这样字典树同一层都是权重相同的。但本题要比较字典序，需要最高位的 1 对齐，不能在前面补 0，例如要比较 11 和 101 的字典序，不能弄成了比较 011 和 101 的字典序。

  • 插入数字 x 时，要先处理出 x 的二进制（不含前导 0，最高位是 1）。这里给出参考写法：

    // 将x转换为二进制，用字符串储存比较方便
    string binaryString(ll x) {string s;do{s += x % 2 + '0';x /= 2;} while (x);reverse(s.begin(), s.end()); // 将逆序的二进制反转为正序return s;
    }
    

  • 对于操作 1，将数字 x 的二进制串 s 从高位往低位插入字典树。

  • 对于操作 2，查找字典树中有多少个二进制串字典序 < x 的二进制串 s 。提示：

    • 如果 s 的某一位是 1，那么与s前面相同，这一位是 0 的字符串字典序都 < s
    • 此外，s 的真前缀（除了 s 本身的 s 的前缀）字典序也比 s 小，例如 11 的字典序 < 110

    int query(string s) {int u = 0, res = 0;for (int i = 0; i < s.size(); ++i) {res += trie[u].cnt;  // s 前缀比 s 小int p = s[i] - '0';// 如果朝右走，加上左子树中单词数量if (p == 1) res += trie[trie[u].ch[0]].siz;if (!trie[u].ch[p]) return res;u = trie[u].ch[p];}return res;
    }
    

Secret Message

• 分析：
  • 本题题意是对于每条暗号 s，查询前面的 n 条信息中，有多少条信息满足 “前缀有 s” 或 “是 s 的前缀”，即课堂代码中的 query2(s) + query3(s) 。
  • 但直接 query2(s) + query3(s) 会有问题，走到结尾结点 u 时，u 的 siz 是包含了 u 的 cnt 的，这样算就会重复统计 u 的 cnt，思考怎么避免重复计算