跳转至

可持久化字典树⚓︎

可持久化字典树（\text{Persistent Trie}）是一种支持版本控制的字典树数据结构。它允许在插入或修改字符串时，保留之前版本的状态，从而可以访问历史版本的数据。

可持久化字典树的实现⚓︎

类似可持久化线段树，每次插入或删除字符串时，只需克隆受影响的节点，从而实现版本的持久化。未被修改的节点可以共享。

字符串树

给定一棵有 N 个节点的树，每条边上都有一个字符串作为标签。现在有 Q 个查询，每个查询给出两个节点 u 和 v 以及一个字符串 s，要求计算从节点 u 到节点 v 的路径上，标签中以字符串 s 作为前缀的边的数量。

Hint

查询从根节点到节点 u 和节点 v 的路径上满足条件的边的数量，然后减去从根节点到它们的最近公共祖先节点 lca(u, v) 的路径上满足条件的边的数量的两倍。

C++
#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <vector>
using namespace std;

struct node {
  array<int, 26> children;
  int pass;
};

vector<node> nodes;  // 所有节点

struct p_trie {
  p_trie() {
    nodes.clear();               // 清空节点
    nodes.emplace_back(node{});  // 占位, 节点编号从1开始
  }

  static int clone(int i) {
    int new_node = nodes.size();   // 新节点编号
    nodes.emplace_back(nodes[i]);  // 克隆当前节点
    return new_node;
  }

  // 插入一个数字, 返回新版本的根节点
  static int insert(const string &s, int i) {
    int new_node          = clone(i);  // 克隆当前节点
    nodes[new_node].pass += 1;
    for (int j = 0, last = new_node; j < s.size(); ++j) {
      int index                    = s[j] - 'a';
      i                            = nodes[last].children[index];
      int new_child                = clone(i);
      nodes[new_child].pass       += 1;
      nodes[last].children[index]  = new_child;
      last                         = new_child;
    }
    return new_node;
  }

  // 查询字符串出现的次数
  static int query(const string &s, int i) {
    for (char ch : s) {
      int index = ch - 'a';
      i         = nodes[i].children[index];
      if (i == 0) { return 0; }
    }
    return nodes[i].pass;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int n;
  cin >> n;

  vector<vector<int>> tree(n + 1);
  map<pair<int, int>, string> edge_labels;

  for (int i = 1; i < n; ++i) {
    int u, v;
    string label;
    cin >> u >> v >> label;
    tree[u].emplace_back(v);
    tree[v].emplace_back(u);
    edge_labels[{min(u, v), max(u, v)}] = label;
  }
  // 可持久化字典树
  p_trie trie;
  vector<int> roots(n + 1);
  // 构建倍增数组和深度数组
  int m = 32 - __builtin_clz(n + 1);
  vector<vector<int>> st(n + 1, vector<int>(m, -1));
  vector<int> depth(n + 1);

  auto dfs = [&](auto &&self, int x, int from) -> void {
    st[x][0] = from;
    for (int y : tree[x]) {
      if (y != from) {
        string &label = edge_labels[{min(x, y), max(x, y)}];
        roots[y]      = p_trie::insert(label, roots[x]);
        depth[y]      = depth[x] + 1;
        self(self, y, x);
      }
    }
  };
  dfs(dfs, 1, -1);
  for (int j = 1; j < m; ++j) {
    for (int i = 1; i <= n; ++i) {
      if (st[i][j - 1] != -1) { st[i][j] = st[st[i][j - 1]][j - 1]; }
    }
  }
  // LCA相关操作
  auto get_kth_ancestor = [&](int node, int k) -> int {
    for (; (k != 0) && (node != -1); k &= k - 1) { node = st[node][__builtin_ctz(k)]; }
    return node;
  };
  auto get_lca = [&](int x, int y) -> int {
    if (depth[x] > depth[y]) { swap(x, y); }
    y = get_kth_ancestor(y, depth[y] - depth[x]);
    if (y == x) { return x; }
    for (int i = m - 1; i >= 0; --i) {
      int px = st[x][i];
      int py = st[y][i];
      if (px != py) {
        x = px;
        y = py;
      }
    }
    return st[x][0];
  };

  int q;
  cin >> q;
  for (int i = 0; i < q; ++i) {
    int u, v;
    string s;
    cin >> u >> v >> s;
    int lca          = get_lca(u, v);
    int count_in_v   = p_trie::query(s, roots[v]);
    int count_in_u   = p_trie::query(s, roots[u]);
    int count_in_lca = p_trie::query(s, roots[lca]);
    cout << count_in_v + count_in_u - count_in_lca * 2 << "\n";
  }

  return 0;
}

可持久化0-1字典树⚓︎

可持久化 \text{0-1} 字典树是一种特殊的字典树，主要用于存储二进制字符串（由 0 和 1 组成的字符串）。它支持插入、删除和查询操作，同时保留历史版本的信息。

最大异或和

给定一个非负数组 a，初始长度为 N。有 M 个操作，有以下两种操作类型：

  1. 添加操作：表示在序列末尾添加一个数 x，序列的长度 N 加 1。
  2. 询问操作：找到一个位置 p，满足 l \leq p \leq r，使得：a[p] \oplus a[p+1] \oplus \dots \oplus a[N] \oplus x 最大，输出最大值。
Hint

定义前缀异或数组 eor[i] = a[1] \oplus a[2] \oplus ... \oplus a[i]，那么

a[p] \oplus a[p+1] \oplus ... \oplus a[N] = eor[p-1] \oplus eor[N]

因此，问题转化为在区间 [l-1, r-1] 内寻找一个 eor[i]，使得 eor[i] \oplus eor[N] \oplus x 最大。

使用可持久化 \text{0-1} 字典树存储前缀异或数组 eor 的各个版本。在查询时，利用版本号来限定查询的范围。区间 [l-1, r-1] 对应的版本号为 roots[l-2] 和 roots[r-1]。

Tip

注意区分空版本和 0 版本的区别，空版本表示没有任何数插入，而 0 版本表示插入了数 0。

C++
#include <array>
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

struct node {
  array<int64_t, 2> children;
  int64_t pass;
};

vector<node> nodes;  // 所有节点

struct p_trie {
  const int64_t BIT = 32;  // 假设数字不超过32位

  p_trie() {
    nodes.clear();               // 清空节点
    nodes.emplace_back(node{});  // 占位, 节点编号从1开始
  }

  static int64_t clone(int64_t i) {
    int64_t new_node = nodes.size();  // 新节点编号
    nodes.emplace_back(nodes[i]);     // 克隆当前节点
    return new_node;
  }

  // 插入一个数字, 返回新版本的根节点
  int64_t insert(int64_t num, int64_t i) const {
    int64_t new_node      = clone(i);  // 克隆当前节点
    nodes[new_node].pass += 1;
    for (int64_t bit = BIT - 1, last = new_node; bit >= 0; --bit) {
      int64_t current_bit                = (num >> bit) & 1;
      i                                  = nodes[last].children[current_bit];
      int64_t new_child                  = clone(i);
      nodes[new_child].pass             += 1;
      nodes[last].children[current_bit]  = new_child;
      last                               = new_child;
    }
    return new_node;
  }

  // root_u为版本u的根节点, root_v为版本v的根节点
  int64_t query(int64_t num, int64_t root_u, int64_t root_v) const {
    int64_t result = 0;
    for (int64_t bit = BIT - 1; bit >= 0; --bit) {
      int64_t current_bit = (num >> bit) & 1;
      int64_t desired_bit = current_bit ^ 1;  // 希望走这条路
      int64_t count_in_v  = nodes[nodes[root_v].children[desired_bit]].pass;
      int64_t count_in_u  = nodes[nodes[root_u].children[desired_bit]].pass;
      if (count_in_v - count_in_u > 0) {  // 说明在u-v区间内存在这条路
        result += (1LL << bit);
        root_u  = nodes[root_u].children[desired_bit];
        root_v  = nodes[root_v].children[desired_bit];
      } else {  // 只能走另一条路
        root_u = nodes[root_u].children[current_bit];
        root_v = nodes[root_v].children[current_bit];
      }
    }
    return result;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int64_t n, m;
  cin >> n >> m;
  p_trie trie;
  vector<int64_t> roots(n + 1);

  int64_t eor = 0;
  // 空版本的根节点编号为0
  // 构建0版本
  roots[0] = trie.insert(eor, 0);
  for (int64_t i = 1; i <= n; ++i) {
    int64_t num;
    cin >> num;
    eor      ^= num;
    roots[i]  = trie.insert(eor, roots[i - 1]);
  }

  for (int64_t i = 0; i < m; ++i) {
    char op;
    cin >> op;
    if (op == 'A') {
      int64_t num;
      cin >> num;
      eor ^= num;
      roots.push_back(trie.insert(eor, roots.back()));
    } else if (op == 'Q') {
      int64_t l, r, x;
      cin >> l >> r >> x;
      cout << (trie.query(eor ^ x, l == 1 ? 0 : roots[l - 2], roots[r - 1])) << "\n";
    }
  }
  return 0;
}

评论