AIOJ

Definition

A trie, as its English name suggests, is a tree like a dictionary.

Introduction

First, here is a diagram:

trie1

It can be seen that this trie uses edges to represent letters, and the path from the root to a node 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 reached from node $u$ by character $c$ , or the node for the string represented by node $u$ after appending character $c$ . (The range of $c$ depends on the size of the character set and is not necessarily $0\sim 26$ .)

Sometimes we need to mark which strings have been inserted into the trie. It is enough to mark the node representing the string whenever an insertion is completed.

Implementation

Here is a template encapsulated in a struct:

C++

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 it does not exist, 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];
  }
};

Python

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 it does not exist, 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]

Java

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 Lookup

The most basic application of a trie is checking whether a string has appeared in the “dictionary”.

Then the Incorrect Roll Call Began

You are given $n$ name strings and then perform $m$ roll calls. For each call, answer one of “the name does not exist”, “this is the first time this name has been called”, or “this name has already been called”.

$1\le n\le 10^4$ , $1\le m\le 10^5$ , and the length of every string does not exceed $50$ .

Solution

Build a trie for all names, then query in the trie whether a string exists and whether it has already been called; 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 none of the child nodes of this node has this character, add it and record the node number for the character as ++tot
      if (!ch[u][c]) ch[u][c] = ++tot;
      u = ch[u][c];  // Search one level deeper
    }
    tag[u] = 1;  // Record 1 to indicate that the name whose last character is at node u has not been visited
  }

  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;  // An absent outgoing edge for the corresponding character means that the name does not exist
    }
    if (tag[u] == 1) {
      tag[u] = 2;  // The name whose last character is at node u has already been visited
      puts("OK");
    } else if (tag[u] == 2)  // Already visited; this is a repeated visit
      puts("REPEAT");
    else
      puts("WRONG");
  }

  return 0;
}

AC Automaton

A trie is part of an AC automaton.

Maintaining XOR Extremes

Viewing the binary representation of a number as a string yields a trie with character set $\{0,1\}$ .

BZOJ1954 Longest XOR Path

Given a tree with edge weights, find $(u, v)$ such that the XOR sum of the edge weights on the path from $u$ to $v$ is maximum, and output this maximum. Here, the XOR sum means the XOR of all edge weights.

The number of vertices does not exceed $10^5$ , and edge weights lie in $[0,2^{31})$ .

Solution

Choose an arbitrary root $root$ . Let $T(u, v)$ denote the XOR sum of the edge weights on the path between $u$ and $v$ . Then $T(u,v)=T(root, u)\oplus T(root,v)$ , because the parts above the LCA cancel after being XORed twice.

If all $T(root, u)$ values are inserted into a trie, then for each $T(root, u)$ we can quickly find the $T(root, v)$ that gives the largest XOR with it:

Starting from the root of the trie, if possible, go into the subtree whose current bit differs from that of $T(root, u)$ ; otherwise there is no choice.

The greedy choice is correct because taking this branch makes the current bit $1$ , while not taking it makes the bit $0$ . Higher bits must be prioritized.

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);  // Take the binary digits one by one from high to low
    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, go into the subtree whose current bit differs from the current bit
      u = ch[u][c ^ 1];
      res |= (1 << i);
    } else
      u = ch[u][c];
  }
  ans = max(ans, res);  // Update the answer
}

void add(int u, int v, int w) {  // Add an 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 the 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);  // Add an edge in both directions
    add(v, u, w);
  }

  dfs(1, 0);

  cout << ans;
  return 0;
}

Maintaining XOR Sums

A 01-trie is a trie whose character set is $\{0,1\}$ . A 01-trie can maintain the XOR sum of some numbers, supporting modifications (deletion + reinsertion) and a global increment by one (that is, making all values it maintains increase by 1; essentially, a special modification operation).

To maintain XOR sums, build the trie from the least significant bit to the most significant bit by value.

Convention: in this article, upward from the current node means the path from the current node to the root, while downward means the subtree of the current node.

Insertion & Deletion

To maintain an XOR sum, we only need the parity of the counts of 0 and 1 at each bit. For the number 1, a bit is 1 if and only if the count of 1s at that bit is odd. Keep this sentence in mind: if we only maintain an XOR sum, we need only the number of 1s at each bit; we do not need to know which numbers the trie actually maintains.

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

ch[o][0/1] denotes the two children of node o; ch[o][0] denotes that the next bit is 0, and likewise ch[o][1] denotes that the next bit is 1.
w[o] denotes the number (weight) of values on the edge from node o to its parent. Whenever a number x is inserted, the weights along the path corresponding to the binary decomposition of x in the trie are all increased by +1.
xorv[o] denotes the XOR sum maintained by the subtree rooted at o.

The code for maintaining a node is shown below.

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 is needed; the exact value is unnecessary. This line can of course also be removed, because the text above uses only its parity.
}

The insertion and deletion code is very similar.

The points to note are:

Here, MAXH denotes the depth of the trie, that is, every leaf is forced to have distance MAXH from the root. For some small values, it may not be necessary to build the trie this deep (for example, when inserting the number 4, whose binary representation is 100, inserting the three bits 001 from the root would be enough), but we force MAXH bits to be inserted. This makes carry handling convenient for a global +1. For example, if the original number is 3 (11) and it becomes 4 (100) after incrementing, the carry would be lost if 3 had initially been inserted using only 2 bits.
For insertion and deletion, only the w[] of leaf nodes needs to be modified; maintain it all the way back during the recursion.

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

A global increment by one means making every value in this trie increase by +1.

Formally, suppose the values maintained in the trie are $V_1, V_2, V_3 \dots V_n$ . After a global increment by one, the maintained values should 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

Let us consider how +1 works in binary.

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

Here are a few examples (the number in parentheses is the corresponding decimal number):

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);

The corresponding trie operation is simply to swap its left and right children, then recurse downward along the 0 edge after the swap.

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

Does this definition seem a little strange? Storing the edge weights to the two children at the parent node might be more conventional. However, when swapping the left and right children, storing the distance to the parent at the child node is clearly more convenient.

01-Trie Merging

This means merging the two 01-tries described above while also merging the information they maintain.

There may be relatively few articles about merging tries. In fact, merging tries is very similar in idea to merging segment trees, so you can search for “merging segment trees” to learn how to merge tries.

Merging tries is actually very simple. Consider a function int merge(int a, int b): it receives the node numbers of two trie nodes at the same relative position, and returns the node number after the merge is complete.

Process

How should this be implemented?

There are three cases:

If a has no node at this position, the merged node is b.
If b has no node at this position, the merged node is a.
If both a and b exist, merge the information from b into a. The merged node is a, and then recursively process the left and right children of a.

Note: if the desired merge is to merge a and b into a new tree, a new node can be created and both can be merged into that node; the implementation below only merges the information from b into a.

Implementation

int merge(int a, int b) {
  if (!a) return b;  // If a has no node at this position, return b
  if (!b) return a;  // If b has no node at this position, return a
  /*
    If both `a` and `b` exist,
    merge the information from `b` into `a`.
  */
  w[a] = w[a] + w[b];
  xorv[a] ^= xorv[b];
  /* Do not use maintain(),
    because maintain() merges the information of a's two children,
    whereas here the information of nodes a and b must be merged.
   */
  ch[a][0] = merge(ch[a][0], ch[b][0]);
  ch[a][1] = merge(ch[a][1], ch[b][1]);
  return a;
}

A trie can in fact be merged in general; in other words, trie merging is not limited to 01-tries.

【luogu-P6018】【Ynoi2010】Fusion tree

Given a tree with $n$ nodes, each with a weight, and $m$ operations. The operations must support the following:

For a node $x$ , increase the weight of every node at distance $1$ from it by $+1$ . Here, the distance between two tree nodes is defined as the number of edges on the shortest path from one to the other.
Decrease the weight at node $x$ by $-v$ .
Query the XOR sum of the weights of all nodes from node $x$ at distance $1$ . 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$ , and $opt\in\{1,2,3\}$ . It is guaranteed that the weight of every node is nonnegative at all times.

Solution

Build a trie for the weights of each node's children; the trie should support a global increment by one. A lazy tag can be set at each node to record the increment applied to the weights of its children.

Reference Code

#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]` denotes the number (weight) of values on the edge from node `o` to its parent.
int xorv[_n];
int tot = 0;

void maintain(int o) {  // Maintain the w array and the 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, and 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) {  // Increment all nodes by 1, that is, swap ch[o][1] and ch[o][0]
  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) {  // Compute the fa array
  fa[o] = f;
  for (int i = head[o]; i; i = edge[i].nxt) {  // Traverse the 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);  // Add an undirected edge
    add(rt = v, u);
  }
  dfs0(rt, -1);  // rt is an arbitrary node
  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);  // Insert again
      }
      trie::addall(trie::rt[x]);  // Increment all nodes by 1
    } 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);  // Insert again
    } else {
      int res = 0;
      res = trie::xorv[trie::rt[x]];
      res ^= get(fa[x]);
      cout << res << '\n';
    }
  }
  return 0;
}

【luogu-P6623】【Provincial Selection Contest 2020, A】 Tree

Given a rooted tree with $n$ nodes, denoted $T$ , numbered starting from $1$ , whose root is node $1$ , and where each node has a positive integer weight $v_i$ .
Let the node numbers of all nodes in the subtree of node $x$ (including $x$ itself) be $c_1,c_2,\dots,c_k$ , and 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 node $x$ and node $y$ in the tree, $d(x,x) = 0$ , and $\oplus$ denotes the XOR operation. Find the result of $\sum\limits_{i=1}^n val(i)$ .

Solution

Consider the contribution of each node to all of its ancestors. For each node, build a trie initially containing only that node's weight; then merge the tries of its children from the bottom up, apply a global increment by one, and finally accumulate 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.