Skip to content

Persistent Trie

Introduction

The approach to persistent Trie is similar to that of persistent segment trees: only modify the nodes that are added or have their values changed, while preserving the unmodified nodes, linking edges based on the previous version, so that the Trie tree traversable from the root of each version is complete and contains all information.

In most persistent Trie problems, the Trie appears in the form of a 01-Trie.

Example Problem Maximum XOR Sum

Given an array \(a\) of length \(n\), perform the following operations:

  1. Append a number \(x\) to the end of the array, increasing the length \(n\) by \(1\).
  2. Given a query interval \([l,r]\) and a value \(k\), find the maximum value of \(k \oplus \bigoplus^{n}_{i=p} a_i\) when \(l\le p\le r\).

Process

The value to be computed may seem complicated. Using the common method for handling consecutive XOR, let \(s_x=\bigoplus_{i=1}^x a_i\), then the original expression is equivalent to \(s_{p-1}\oplus s_n\oplus k\). Observe that \(s_n \oplus k\) is fixed during the query, so the query essentially becomes finding the maximum XOR with a fixed value (\(s_n\oplus k\)) in the interval \([l-1,r-1]\).

Continuing with an approach similar to persistent segment trees, consider that each query covers the entire interval. We only need to build a Trie tree for this interval, insert every number in this interval into the Trie, and during the query, try to traverse to the branch that differs from the current bit as much as possible.

To query an interval, we can use the idea of prefix sums and difference: subtract two prefix Trie trees (i.e., two historical versions added in order) to obtain the Trie tree for that interval. Additionally, using the idea of dynamic node creation, we avoid adding nodes that have not been computed to save space.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
constexpr int MAXN = 600010;
int n, q, a[MAXN], s[MAXN], l, r, x;
char op;

struct Trie {
  int cnt, rt[MAXN], ch[MAXN * 33][2], val[MAXN * 33];

  void insert(int o, int lst, int v) {
    for (int i = 28; i >= 0; i--) {
      val[o] = val[lst] + 1;  // Update based on the original version
      if ((v & (1 << i)) == 0) {
        if (!ch[o][0]) ch[o][0] = ++cnt;
        ch[o][1] = ch[lst][1];
        o = ch[o][0];
        lst = ch[lst][0];
      } else {
        if (!ch[o][1]) ch[o][1] = ++cnt;
        ch[o][0] = ch[lst][0];
        o = ch[o][1];
        lst = ch[lst][1];
      }
    }
    val[o] = val[lst] + 1;
  }

  int query(int o1, int o2, int v) {
    int ret = 0;
    for (int i = 28; i >= 0; i--) {
      int t = ((v & (1 << i)) ? 1 : 0);
      if (val[ch[o1][!t]] - val[ch[o2][!t]])
        ret += (1 << i), o1 = ch[o1][!t],
                         o2 = ch[o2][!t];  // Try to jump to the different branch
      else
        o1 = ch[o1][t], o2 = ch[o2][t];
    }
    return ret;
  }
} st;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) cin >> a[i], s[i] = s[i - 1] ^ a[i];
  for (int i = 1; i <= n; i++)
    st.rt[i] = ++st.cnt, st.insert(st.rt[i], st.rt[i - 1], s[i]);
  while (q--) {
    cin >> op;
    if (op == 'A') {
      n++;
      cin >> a[n];
      s[n] = s[n - 1] ^ a[n];
      st.rt[n] = ++st.cnt;
      st.insert(st.rt[n], st.rt[n - 1], s[n]);
    }
    if (op == 'Q') {
      cin >> l >> r >> x;
      l--;
      r--;
      if (l == 0)
        cout << max(s[n] ^ x, st.query(st.rt[r], st.rt[0], s[n] ^ x)) << '\n';
      else
        cout << st.query(st.rt[r], st.rt[l - 1], s[n] ^ x) << '\n';
    }
  }
  return 0;
}

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