Bỏ qua

Persistent Trie

Giới thiệu

Phương pháp Trie bền vững tương tự như Cây phân đoạn bền vững, tức là mỗi lần chỉ sửa đổi các nút được thêm hoặc giá trị bị thay đổi, trong khi giữ lại các nút không thay đổi, nối các cạnh dựa trên phiên bản trước đó, sao cho cuối cùng mỗi phiên bản của Trie gốc đều hoàn chỉnh và chứa đầy đủ thông tin.

Trong hầu hết các bài toán Trie bền vững, Trie xuất hiện dưới dạng 01-Trie.

Ví dụ Maximum XOR Sum

Cho một mảng \(a\) có độ dài \(n\), thực hiện các thao tác sau:

  1. Thêm một số \(x\) vào cuối mảng, độ dài mảng \(n\) tăng thêm \(1\).
  2. Cho khoảng truy vấn \([l,r]\) và một giá trị \(k\), tìm giá trị lớn nhất của \(k \oplus \bigoplus^{n}_{i=p} a_i\) với \(l\le p\le r\).

Quá trình

Giá trị cần tìm có vẻ hơi phức tạp, sử dụng phương pháp xử lý XOR liên tiếp thường dùng, ký hiệu \(s_x=\bigoplus_{i=1}^x a_i\), thì biểu thức ban đầu tương đương với \(s_{p-1}\oplus s_n\oplus k\). Nhận thấy rằng \(s_n \oplus k\) là cố định trong quá trình truy vấn, bài toán truy vấn chuyển thành tìm giá trị lớn nhất khi XOR với một giá trị cố định (\(s_n\oplus k\)) trong khoảng \([l-1,r-1]\).

Tiếp tục theo ý tưởng tương tự như Cây phân đoạn bền vững, hãy xem xét mỗi lần truy vấn là truy vấn trên toàn bộ khoảng. Chúng ta chỉ cần xây dựng một Trie cho khoảng này, thêm mỗi số trong khoảng này vào Trie, khi truy vấn thì cố gắng nhảy đến nhánh có bit khác với bit hiện tại.

Để truy vấn khoảng, chỉ cần sử dụng ý tưởng tổng tiền tố và hiệu, dùng hai cây Trie tiền tố (tức là hai phiên bản lịch sử thêm số theo thứ tự) trừ đi nhau để có được cây Trie của khoảng đó. Sử dụng ý tưởng cấp phát động, không thêm các điểm chưa tính toán để giảm dung lượng bộ nhớ.

 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;  // 在原版本的基础上更新
      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];  // 尽量向不同的地方跳
      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;
}

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:OI-wiki
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply