Trie

Definition

A trie, also known as a prefix tree, is a tree-like data structure that resembles a dictionary.

Introduction

First, look at an image:

It can be observed that this trie uses edges to represent letters, and the path from the root node to any node on the tree represents a string. For example, \(1\to4\to 8\to 12\) represents the string caa.

The structure of a trie is very intuitive. We use \(\delta(u,c)\) to denote the next node pointed to by character \(c\) from node \(u\), or equivalently, the node representing the string formed by appending character \(c\) to the string represented by node \(u\). (The range of \(c\) depends on the size of the character set and is not necessarily \(0\sim 26\).)

Sometimes it is necessary to mark which strings have been inserted into the trie. This can be done by marking the node representing the string after each insertion.

Implementation

Here is a template encapsulated in a structure:

C++PythonJava

struct trie {
  int nex[100000][26], cnt;
  bool exist[100000];  // Whether a string ending at this node exists

  void insert(char *s, int l) {  // Insert a string
    int p = 0;
    for (int i = 0; i < l; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) nex[p][c] = ++cnt;  // If not present, add a node
      p = nex[p][c];
    }
    exist[p] = true;
  }

  bool find(char *s, int l) {  // Find a string
    int p = 0;
    for (int i = 0; i < l; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) return 0;
      p = nex[p][c];
    }
    return exist[p];
  }
};

class trie:
    def __init__(self):
        self.nex = [[0 for i in range(26)] for j in range(100000)]
        self.cnt = 0
        self.exist = [False] * 100000  # Whether a string ending at this node exists

    def insert(self, s):  # Insert a string
        p = 0
        for i in s:
            c = ord(i) - ord("a")
            if not self.nex[p][c]:
                self.cnt += 1
                self.nex[p][c] = self.cnt  # If not present, add a node
            p = self.nex[p][c]
        self.exist[p] = True

    def find(self, s):  # Find a string
        p = 0
        for i in s:
            c = ord(i) - ord("a")
            if not self.nex[p][c]:
                return False
            p = self.nex[p][c]
        return self.exist[p]

public class Trie {
    int[][] tree = new int[10000][26];
    int cnt = 0;
    boolean[] end = new boolean[10000];

    public void insert(String word) {
        int p = 0;
        char[] chars = word.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            int c = chars[i] - 'a';
            if (tree[p][c] == 0) {
                tree[p][c] = ++cnt;
            }
            p = tree[p][c];
        }
        end[p] = true;
    }

    public boolean find(String word) {
        int p = 0;
        char[] chars = word.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            int c = chars[i] - 'a';
            if (tree[p][c] == 0) {
                return false;
            }
            p = tree[p][c];
        }
        return end[p];
    }
}

Applications

String Retrieval

The most basic application of a trie—checking whether a string appears in the "dictionary."

Thus Begins the Wrong Roll Call

You are given \(n\) name strings, followed by \(m\) roll calls. For each call, you need to answer one of: "name does not exist", "first time calling this name", or "already called this name".

\(1\le n\le 10^4\), \(1\le m\le 10^5\), all strings have length at most \(50\).

Solution

Build a trie for all names, then query the trie to check if the string exists and whether it has been called before. Mark it as called on the first call.

Reference Code

#include <cstdio>
using namespace std;
constexpr int N = 500010;

char s[N];
int n, m, ch[N][26], tag[N], tot = 1;

int main() {
  scanf("%d", &n);

  for (int i = 1; i <= n; ++i) {
    scanf("%s", s + 1);
    int u = 1;
    for (int j = 1; s[j]; ++j) {
      int c = s[j] - 'a';
      // If this node's child does not have this character, add it and record the node number of this character as ++tot
      if (!ch[u][c]) ch[u][c] = ++tot;
      u = ch[u][c];  // Search deeper
    }
    tag[u] = 1;  // Mark the last character node u as unvisited (record as 1)
  }

  scanf("%d", &m);

  while (m--) {
    scanf("%s", s + 1);
    int u = 1;
    for (int j = 1; s[j]; ++j) {
      int c = s[j] - 'a';
      u = ch[u][c];
      if (!u) break;  // If there is no outgoing edge for the corresponding character, the name does not exist
    }
    if (tag[u] == 1) {
      tag[u] = 2;  // The name ending at node u has been visited
      puts("OK");
    } else if (tag[u] == 2)  // Already visited, repeated access
      puts("REPEAT");
    else
      puts("WRONG");
  }

  return 0;
}

Aho-Corasick Automaton

The trie is a part of the Aho-Corasick automaton.

Maintaining XOR Extremes

Treating the binary representation of numbers as strings allows building a trie with character set \(\{0,1\}\).

BZOJ1954 Longest XOR Path

Given a tree with weighted edges, find \((u, v)\) such that the XOR sum of edge weights on the path from \(u\) to \(v\) is maximized, and output this maximum value. The XOR sum refers to the XOR of all edge weights.

The number of nodes does not exceed \(10^5\), and edge weights are in \([0,2^{31})\).

Solution

Arbitrarily choose a root \(root\). Let \(T(u, v)\) denote the XOR sum of edge weights on the path between \(u\) and \(v\). Then \(T(u,v)=T(root, u)\oplus T(root,v)\), because the part above the LCA cancels out after XORing twice.

If all \(T(root, u)\) are inserted into a trie, for each \(T(root, u)\), we can quickly find the \(T(root, v)\) that maximizes the XOR sum with it:

Starting from the root of the trie, if possible, go to the subtree corresponding to the opposite bit of the current bit of \(T(root, u)\); otherwise, there is no choice.

The correctness of the greedy approach: If we go this way, this bit becomes \(1\); otherwise, it becomes \(0\). Higher bits should be prioritized to be as large as possible.

Reference Code

#include <algorithm>
#include <iostream>
using namespace std;

constexpr int N = 100010;

int head[N], nxt[N << 1], to[N << 1], weight[N << 1], cnt;
int n, dis[N], ch[N << 5][2], tot = 1, ans;

void insert(int x) {
  for (int i = 30, u = 1; i >= 0; --i) {
    int c = ((x >> i) & 1);  // Extract bits one by one from binary
    if (!ch[u][c]) ch[u][c] = ++tot;
    u = ch[u][c];
  }
}

void get(int x) {
  int res = 0;
  for (int i = 30, u = 1; i >= 0; --i) {
    int c = ((x >> i) & 1);
    if (ch[u][c ^ 1]) {  // If possible to go to the subtree with the opposite bit, go there
      u = ch[u][c ^ 1];
      res |= (1 << i);
    } else
      u = ch[u][c];
  }
  ans = max(ans, res);  // Update answer
}

void add(int u, int v, int w) {  // Add edge
  nxt[++cnt] = head[u];
  head[u] = cnt;
  to[cnt] = v;
  weight[cnt] = w;
}

void dfs(int u, int fa) {
  insert(dis[u]);
  get(dis[u]);
  for (int i = head[u]; i; i = nxt[i]) {  // Traverse child nodes
    int v = to[i];
    if (v == fa) continue;
    dis[v] = dis[u] ^ weight[i];
    dfs(v, u);
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n;

  for (int i = 1; i < n; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    add(u, v, w);  // Bidirectional edge
    add(v, u, w);
  }

  dfs(1, 0);

  cout << ans;
  return 0;
}

Maintaining XOR Sum

A 01-trie is a trie with character set \(\{0,1\}\). It can be used to maintain the XOR sum of some numbers, supporting modifications (deletion + reinsertion) and global increment by one (i.e., increment all maintained values by 1, which is essentially a special type of modification).

To maintain the XOR sum, the trie should be built from the least significant bit to the most significant bit.

A convention: In this context, "upward" refers to the path from the current node to the root, and "downward" refers to the subtree of the current node.

Insertion & Deletion

To maintain the XOR sum, we only need to know the parity of the counts of 0s and 1s at each bit. That is, for bit 1, the bit is 1 if and only if the number of 1s at this bit is odd. Remember this: if we are only maintaining the XOR sum, we only need to know the count of 1s at each bit, not the actual numbers maintained by the trie.

For each node, we need to maintain the following three quantities:

• ch[o][0/1] refers to the two children of node o. ch[o][0] corresponds to the next bit being 0, and similarly ch[o][1] corresponds to the next bit being 1.
• w[o] denotes the weight (count) on the edge from node o to its parent. For each inserted number x, the weight on the path corresponding to the binary representation of x in the trie is incremented by 1.
• xorv[o] is the XOR sum maintained by the subtree rooted at o.

The code for maintaining node information is as follows:

void maintain(int o) {
  w[o] = xorv[o] = 0;
  if (ch[o][0]) {
    w[o] += w[ch[o][0]];
    xorv[o] ^= xorv[ch[o][0]] << 1;
  }
  if (ch[o][1]) {
    w[o] += w[ch[o][1]];
    xorv[o] ^= (xorv[ch[o][1]] << 1) | (w[ch[o][1]] & 1);
  }
  // w[o] = w[o] & 1;
  // Only the parity matters, not the exact value. This line can be omitted since only parity is used above.
}

The code for insertion and deletion is very similar.

Points to note:

• Here, MAXH refers to the depth of the trie, i.e., forcing every leaf node to be at distance MAXH from the root. For smaller values, such depth may not be necessary (e.g., inserting the number 4, which is 100 in binary, only requires inserting 001 from the root). However, we force insertion to MAXH bits. This is to facilitate handling carry during global +1. For example, if the original number is 3 (11), after incrementing it becomes 4 (100). If only 2 bits were inserted for 3, the carry would be lost.

• For insertion and deletion, only the w[] of leaf nodes needs to be modified, and the information is maintained during backtracking.

Implementation

namespace trie {
constexpr int MAXH = 21;
int ch[_ * (MAXH + 1)][2], w[_ * (MAXH + 1)], xorv[_ * (MAXH + 1)];
int tot = 0;

int mknode() {
  ++tot;
  ch[tot][1] = ch[tot][0] = w[tot] = xorv[tot] = 0;
  return tot;
}

void maintain(int o) {
  w[o] = xorv[o] = 0;
  if (ch[o][0]) {
    w[o] += w[ch[o][0]];
    xorv[o] ^= xorv[ch[o][0]] << 1;
  }
  if (ch[o][1]) {
    w[o] += w[ch[o][1]];
    xorv[o] ^= (xorv[ch[o][1]] << 1) | (w[ch[o][1]] & 1);
  }
  w[o] = w[o] & 1;
}

void insert(int &o, int x, int dp) {
  if (!o) o = mknode();
  if (dp > MAXH) return (void)(w[o]++);
  insert(ch[o][x & 1], x >> 1, dp + 1);
  maintain(o);
}

void erase(int o, int x, int dp) {
  if (dp > 20) return (void)(w[o]--);
  erase(ch[o][x & 1], x >> 1, dp + 1);
  maintain(o);
}
}  // namespace trie

Global Increment by One

Global increment by one means adding 1 to all values maintained in the trie.

Formally, let the values maintained in the trie be \(V_1, V_2, V_3 \dots V_n\). After global increment by one, the values become \(V_1+1, V_2+1, V_3+1 \dots V_n+1\).

void addall(int o) {
  swap(ch[o][0], ch[o][1]);
  if (ch[o][0]) addall(ch[o][0]);
  maintain(o);
}

Process

Consider how +1 operates in binary.

We only need to find the first 0 from the least significant bit to the most significant bit, change it to 1, and then change all 1s after this position to 0.

Here are some examples (numbers in parentheses are their decimal equivalents):

1000(8)  + 1 = 1001(9)  ;
10011(19) + 1 = 10100(20) ;
11111(31) + 1 = 100000(32);
10101(21) + 1 = 10110(22) ;
100000000111111(16447) + 1 = 100000001000000(16448);

Corresponding trie operations involve swapping left and right children and recursively operating along the swapped 0 edge.

Recall the definition of w[o]: w[o] denotes the weight (count) on the edge from node o to its parent.

Does this definition feel odd? It might be more intuitive to store the edge weights from the parent to its two children at the parent node. However, here, storing the distance to the parent at the child node is more convenient when swapping left and right children.

01-Trie Merging

This refers to merging two 01-tries while combining the maintained information.

There may be few articles about merging tries. Actually, merging tries is very similar to merging segment trees. You can search for "merging segment trees" to learn how to merge tries.

Merging tries is straightforward. Consider a function int merge(int a, int b) that takes the node indices of two tries at the same relative position and returns the node index after merging.

Process

How to implement it?

Consider three cases:

• If a does not have a node at this position, the merged node is b.
• If b does not have a node at this position, the merged node is a.

• If both a and b exist, merge the information of b into a. The merged node is a, and then recursively process the children of a.

  Hint: If the requirement is to merge a and b into a new tree, you can create a new node and merge into it. The code here only merges b's information into a.

Implementation

int merge(int a, int b) {
  if (!a) return b;  // If a does not have a node at this position, return b
  if (!b) return a;  // If b does not have a node at this position, return a
  /*
    If both `a` and `b` exist,
    merge the information of `b` into `a`.
  */
  w[a] = w[a] + w[b];
  xorv[a] ^= xorv[b];
  /* Do not use maintain(),
    maintain() merges information of a's two children
    Here we need to merge information of nodes a and b.
   */
  ch[a][0] = merge(ch[a][0], ch[b][0]);
  ch[a][1] = merge(ch[a][1], ch[b][1]);
  return a;
}

Actually, any trie can be merged. In other words, trie merging is not limited to 01-tries.

【luogu-P6018】【Ynoi2010】Fusion tree

You are given a tree with \(n\) nodes, each node has a weight. There are \(m\) operations. Support the following operations:

• Increment the weights of all nodes at distance \(1\) from node \(x\) by \(1\). Here, the distance between two nodes on the tree is defined as the number of edges on the shortest path from one node to the other.

• Decrease the weight of node \(x\) by \(v\).

• Query the XOR sum of the weights of all nodes at distance \(1\) from node \(x\). For \(100\%\) of the data, \(1\le n \le 5\times 10^5\), \(1\le m \le 5\times 10^5\), \(0\le a_i \le 10^5\), \(1 \le x \le n\), \(opt\in\{1,2,3\}\). Ensure that the weight of each node is non-negative at all times.

Solution

Each node maintains a trie for the weights of its children. The trie should support global increment by one. Lazy tags can be used at each node to mark the increment amount for children's weights.

Reference Code

```cpp
#include <iostream>
using namespace std;
constexpr int _ = 5e5 + 10;

namespace trie {
constexpr int _n = _ * 25;
int rt[_];
int ch[_n][2];
int w[_n];  // `w[o]` indicates the number of values (weight) on the edge from node `o` to its parent.
int xorv[_n];
int tot = 0;

void maintain(int o) {  // Maintain the w array and xorv (XOR of weights) array
  w[o] = xorv[o] = 0;
  if (ch[o][0]) {
    w[o] += w[ch[o][0]];
    xorv[o] ^= xorv[ch[o][0]] << 1;
  }
  if (ch[o][1]) {
    w[o] += w[ch[o][1]];
    xorv[o] ^= (xorv[ch[o][1]] << 1) | (w[ch[o][1]] & 1);
  }
}

int mknode() {  // Create a new node
  ++tot;
  ch[tot][0] = ch[tot][1] = 0;
  w[tot] = 0;
  return tot;
}

void insert(int &o, int x, int dp) {  // x is the weight, dp is the depth
  if (!o) o = mknode();
  if (dp > 20) return (void)(w[o]++);
  insert(ch[o][x & 1], x >> 1, dp + 1);
  maintain(o);
}

void erase(int o, int x, int dp) {
  if (dp > 20) return (void)(w[o]--);
  erase(ch[o][x & 1], x >> 1, dp + 1);
  maintain(o);
}

void addall(int o) {  // Add 1 to all nodes, i.e., swap ch[o][1] and ch[o][0] for all nodes
  swap(ch[o][1], ch[o][0]);
  if (ch[o][0]) addall(ch[o][0]);
  maintain(o);
}
}  // namespace trie

int head[_];

struct edges {
  int node;
  int nxt;
} edge[_ << 1];

int tot = 0;

void add(int u, int v) {
  edge[++tot].nxt = head[u];
  head[u] = tot;
  edge[tot].node = v;
}

int n, m;
int rt;
int lztar[_];
int fa[_];

void dfs0(int o, int f) {  // Obtain the fa array
  fa[o] = f;
  for (int i = head[o]; i; i = edge[i].nxt) {  // Traverse child nodes
    int node = edge[i].node;
    if (node == f) continue;
    dfs0(node, o);
  }
}

int V[_];

// Weight function
int get(int x) { return (fa[x] == -1 ? 0 : lztar[fa[x]]) + V[x]; }

int main() {
  cin >> n >> m;
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    add(u, v);  // Build bidirectional edge
    add(rt = v, u);
  }
  dfs0(rt, -1);  // rt is a randomly chosen point
  for (int i = 1; i <= n; i++) {
    cin >> V[i];
    if (fa[i] != -1) trie::insert(trie::rt[fa[i]], V[i], 0);
  }
  while (m--) {
    int opt, x;
    cin >> opt >> x;
    if (opt == 1) {
      lztar[x]++;
      if (x != rt) {
        if (fa[fa[x]] != -1) trie::erase(trie::rt[fa[fa[x]]], get(fa[x]), 0);
        V[fa[x]]++;
        if (fa[fa[x]] != -1)
          trie::insert(trie::rt[fa[fa[x]]], get(fa[x]), 0);  // Re-insert
      }
      trie::addall(trie::rt[x]);  // Add 1 to all nodes
    } else if (opt == 2) {
      int v;
      cin >> v;
      if (x != rt) trie::erase(trie::rt[fa[x]], get(x), 0);
      V[x] -= v;
      if (x != rt) trie::insert(trie::rt[fa[x]], get(x), 0);  // Re-insert
    } else {
      int res = 0;
      res = trie::xorv[trie::rt[x]];
      res ^= get(fa[x]);
      cout << res << '\n';
    }
  }
  return 0;
}

```

【luogu-P6623】【Provincial Selection Joint Exam 2020 A Volume】Tree

Given a rooted tree \(T\) with \(n\) nodes, nodes are numbered starting from \(1\), and the root is node \(1\). Each node has a positive integer weight \(v_i\). Let the nodes in the subtree of node \(x\) (including \(x\) itself) be \(c_1,c_2,\dots,c_k\). Define the value of \(x\) as:
\(val(x)=(v_{c_1}+d(c_1,x)) \oplus (v_{c_2}+d(c_2,x)) \oplus \cdots \oplus (v_{c_k}+d(c_k, x))\) where \(d(x,y)\)
denotes the number of edges on the unique simple path between nodes \(x\) and \(y\) on the tree, and \(d(x,x) = 0\). \(\oplus\) denotes the XOR operation. Please compute \(\sum\limits_{i=1}^n val(i)\).

Solution

Consider the contribution of each node to all its ancestors. Each node builds a trie, initially containing only its own weight. Then, merge the tries of all child nodes from bottom to top, perform a global increment by one, and then compute the answer.

Reference Code

constexpr int _ = 526010;
int n;
int V[_];
int debug = 0;

namespace trie {
constexpr int MAXH = 21;
int ch[_ * (MAXH + 1)][2], w[_ * (MAXH + 1)], xorv[_ * (MAXH + 1)];
int tot = 0;

int mknode() {
  ++tot;
  ch[tot][1] = ch[tot][0] = w[tot] = xorv[tot] = 0;
  return tot;
}

void maintain(int o) {
  w[o] = xorv[o] = 0;
  if (ch[o][0]) {
    w[o] += w[ch[o][0]];
    xorv[o] ^= xorv[ch[o][0]] << 1;
  }
  if (ch[o][1]) {
    w[o] += w[ch[o][1]];
    xorv[o] ^= (xorv[ch[o][1]] << 1) | (w[ch[o][1]] & 1);
  }
  w[o] = w[o] & 1;
}

void insert(int &o, int x, int dp) {
  if (!o) o = mknode();
  if (dp > MAXH) return (void)(w[o]++);
  insert(ch[o][x & 1], x >> 1, dp + 1);
  maintain(o);
}

int merge(int a, int b) {
  if (!a) return b;
  if (!b) return a;
  w[a] = w[a] + w[b];
  xorv[a] ^= xorv[b];
  ch[a][0] = merge(ch[a][0], ch[b][0]);
  ch[a][1] = merge(ch[a][1], ch[b][1]);
  return a;
}

void addall(int o) {
  swap(ch[o][0], ch[o][1]);
  if (ch[o][0]) addall(ch[o][0]);
  maintain(o);
}
}  // namespace trie

int rt[_];
long long Ans = 0;
vector<int> E[_];

void dfs0(int o) {
  for (int i = 0; i < E[o].size(); i++) {
    int node = E[o][i];
    dfs0(node);
    rt[o] = trie::merge(rt[o], rt[node]);
  }
  trie::addall(rt[o]);
  trie::insert(rt[o], V[o], 0);
  Ans += trie::xorv[rt[o]];
}

int main() {
  n = read();
  for (int i = 1; i <= n; i++) V[i] = read();
  for (int i = 2; i <= n; i++) E[read()].push_back(i);
  dfs0(1);
  printf("%lld", Ans);
  return 0;
}

Persistent Trie

See Persistent Trie.

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用