Cây Trie
Cây Trie là gì?
Cây Trie, hay còn gọi là cây từ điển, là một cấu trúc dữ liệu dạng cây dùng để lưu trữ tập hợp các chuỗi ký tự. Cụ thể, nó có một nút gốc không có ý nghĩa (thường được đánh số là 0 hoặc 1), và tất cả các chuỗi được lưu trữ đều có thể đi theo một đường cố định từ nút gốc xuống và kết nối các ký tự trên các nút.
Các thao tác chèn, xóa và tìm kiếm trong cây Trie
Chèn
Chèn là thao tác phổ biến trong cây Trie, biểu thị việc chèn một chuỗi s vào cây Trie đã chọn.
Giả sử chuỗi s chỉ bao gồm 26 chữ cái nhỏ.
Sử dụng tree[u][v] để biểu thị cạnh trong cây, tức là nút u có một nút con với ký tự v (chữ 'a' đến 'z' được biểu diễn bằng 0 đến 25). tree[u][v] lưu trữ số hiệu của nút con chứa ký tự v.
Khi chèn, ta duyệt qua từng ký tự trong chuỗi s. Nếu nút hiện tại có con chứa ký tự đang xét, ta di chuyển tới nút con đó. Ngược lại, tạo một nút mới và liên kết với nút hiện tại.
Ví dụ mã nguồn (nút gốc là 0):
void Add(string s) {
int now = 0;
for (char c : s) {
int x = c - 'a';
if (!tree[now][x]) tree[now][x] = ++Cnt;
now = tree[now][x];
}
}
Xóa
Xóa khá phức tạp vì một nút có thể chứa nhiều chuỗi khác nhau. Khi xóa, nếu nút vẫn còn chứa chuỗi khác, ta không xóa nút đó.
Để thực hiện điều này, ta cần sửa hàm Add để đếm số lượng chuỗi đi qua mỗi nút. Thêm mảng f để lưu số lượng chuỗi đi qua nút u.
Hàm Add sau khi sửa đổi:
void Add(string s) {
int now = 0;
for (char c : s) {
int x = c - 'a';
if (!tree[now][x]) tree[now][x] = ++Cnt;
now = tree[now][x], f[now]++;
}
}
Khi xóa, ta giảm giá trị f[now] đi 1. Hàm Del:
void Del(string s) {
int now = 0;
for (char c : s) {
int x = c - 'a';
now = tree[now][x], f[now]--;
}
}
Tìm kiếm
Tìm kiếm cơ bản là kiểm tra xem một chuỗi có tồn tại trong cây Trie hay không. Tương tự như hàm Add, nhưng nếu không có cạnh, trả về false.
Mã nguồn:
bool Ask(string s) {
int now = 0;
for (char c : s) {
int x = c - 'a';
if (!tree[now][x] || !f[tree[now][x]]) return false;
now = tree[now][x];
}
return true;
}
Bài toán ví dụ: CF1792D
Đây là một bài toán kinh điển. Ta thấy rõ ràng đây là một cây Trie. Trong hàm Ask, thay vì kiểm tra xem có thể đi đến cuối chuỗi hay không, ta tính số lượng ký tự có thể đi qua.
Mã nguồn:
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int T, n, m, a[N][15], s[N][15], tree[N][15], Cnt;
int read() {
int su = 0, pp = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') pp = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { su = su * 10 + ch - '0'; ch = getchar(); }
return su * pp;
}
void Init() {
for (int i = 0; i <= Cnt; i++)
for (int j = 0; j <= 10; j++) tree[i][j] = 0, s[i][j] = 0;
Cnt = 0;
}
void Add(int id) {
int now = 0;
for (int i = 1; i <= m; i++) cin >> a[id][i];
for (int i = 1; i <= m; i++) s[id][a[id][i]] = i;
for (int i = 1; i <= m; i++) {
int x = s[id][i];
if (!tree[now][x]) tree[now][x] = (++Cnt);
now = tree[now][x];
}
}
int Ask(int id) {
int now = 0, ans = 0;
for (int i = 1; i <= m; i++) {
int x = a[id][i];
if (!tree[now][x]) return ans;
now = tree[now][x], ans++;
}
return ans;
}
int main() {
T = read();
while (T--) {
n = read(), m = read(); Init();
for (int i = 1; i <= n; i++) Add(i);
for (int i = 1; i <= n; i++) cout << Ask(i) << " ";
cout << "\n";
}
return 0;
}
Bài toán ví dụ: AT_agc047_b
Đề bài nói rằng, khi độ dài chuỗi s >= 2, ta có thể xóa một trong hai ký tự đầu tiên. Điều này có nghĩa là, sau khi xóa, chuỗi s' sẽ có ký tự đầu tiên gần giống với chuỗi t.
Mã nguồn:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, Cnt, tree[N][30];
long long f[N], Ans, p[30];
string s[N];
void Add(string str) {
int now = 0;
for (int k = str.size() - 1; k >= 0; k--) {
int x = str[k] - 'a';
if (!tree[now][x]) tree[now][x] = (++Cnt);
now = tree[now][x];
}
f[now]++;
}
long long Ask(string str) {
memset(p, 0, sizeof(p));
for (int k = 0; k < str.size(); k++) p[str[k] - 'a']++;
int now = 0;
long long res = 0;
for (int k = str.size() - 1; k > 0; k--) {
int x = str[k] - 'a';
for (int i = 0; i < 26; i++)
if (p[i]) res += f[tree[now][i]];
now = tree[now][x], p[x]--;
}
return res;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> s[i];
Add(s[i]);
}
for (int i = 1; i <= n; i++) Ans += Ask(s[i]);
cout << Ans << "\n";
return 0;
}
Cây Trie 0/1
Cây Trie 0/1 là gì?
Cây Trie 0/1 là một phiên bản đặc biệt của cây Trie, chỉ lưu trữ hai giá trị 0 và 1. Nó thường được sử dụng để lưu trữ các số nhị phân và giải quyết các bài toán liên quan đến phép toán bit, đặc biệt là phép XOR.
Các thao tác chèn, xóa và tìm kiếm trong cây Trie 0/1
Cây Trie 0/1 tương tự như cây Trie thông thường, nhưng có một số điểm khác biệt:
- Thao tác chèn, xóa và tìm kiếm thường bắt đầu từ bit cao nhất và đi xuống.
- Mảng
treechỉ cần kích thước 2 cho mỗi nút.
Bài toán ví dụ: CF665E
Mã nguồn:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5, M = 3e7 + 5;
int n, tree[M][2], Cnt = 1;
long long k, a[N], sum, f[M], Ans;
long long read() {
long long su = 0, pp = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') pp = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { su = su * 10 + ch - '0'; ch = getchar(); }
return su * pp;
}
void Add(long long num) {
long long now = 1;
for (long long i = 30; i >= 0; i--) {
long long x = (num >> i) & 1;
if (!tree[now][x]) tree[now][x] = (++Cnt);
now = tree[now][x], f[now]++;
}
}
long long Ask(long long A, long long B) {
long long now = 1, res = 0;
for (long long i = 30; i >= 0; i--) {
long long x = (A >> i) & 1, y = (B >> i) & 1;
if (y) now = tree[now][1 - x];
else res += f[tree[now][1 - x]], now = tree[now][x];
}
return res + f[now];
}
int main() {
n = read(), k = read();
for (long long i = 1; i <= n; i++) {
a[i] = read();
Add(sum), sum ^= a[i];
Ans += Ask(sum, k);
}
cout << Ans << "\n";
return 0;
}
Bài toán ví dụ: CF1980G
Mã nguồn:
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
struct line { long long v, w; };
int T, n, Q, Cnt[2], tree[2][N * 35][2], f[2][N * 35];
long long dis[N], Xor;
bool p[N];
vector<line> g[N];
long long read() {
long long su = 0, pp = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') pp = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { su = su * 10 + ch - '0'; ch = getchar(); }
return su * pp;
}
void DFS(int u, int fa) {
p[u] = !p[fa];
for (auto [v, w] : g[u]) if (v != fa)
dis[v] = dis[u] ^ w, DFS(v, u);
}
void Add(long long num, int opt) {
long long now = 1;
for (long long i = 32; i >= 0; i--) {
long long x = (num >> i) & 1;
if (!tree[opt][now][x]) tree[opt][now][x] = (++Cnt[opt]);
now = tree[opt][now][x], f[opt][now]++;
}
}
void Del(long long num, int opt) {
long long now = 1;
for (long long i = 32; i >= 0; i--) {
long long x = (num >> i) & 1;
now = tree[opt][now][x], f[opt][now]--;
}
}
long long Ask(long long num, int opt) {
long long now = 1, res = 0;
for (long long i = 32; i >= 0; i--) {
long long x = (num >> i) & 1;
if (tree[opt][now][1 - x] && f[opt][tree[opt][now][1 - x]])
now = tree[opt][now][1 - x], res += (1 << i);
else now = tree[opt][now][x];
}
return res;
}
int main() {
T = read();
while (T--) {
n = read(), Q = read(), Xor = 0;
for (int o = 0; o <= 1; o++) for (int i = 1; i <= Cnt[o]; i++)
tree[o][i][0] = 0, tree[o][i][1] = 0, f[o][i] = 0;
Cnt[0] = 1, Cnt[1] = 1;
for (int i = 1; i <= n; i++) g[i].clear();
for (int i = 1; i < n; i++) {
int x = read(), y = read(), z = read();
g[x].push_back({y, z}), g[y].push_back({x, z});
}
p[0] = 1, DFS(1, 0);
for (int i = 1; i <= n; i++) Add(dis[i], p[i]);
while (Q--) {
char opt; cin >> opt;
if (opt == '^') { Xor ^= read(); continue; }
long long u = read(), x = read(); Del(dis[u], p[u]);
long long Ans = max(Ask(dis[u] ^ x, p[u]), Ask(dis[u] ^ x ^ Xor, !p[u]));
cout << Ans << " "; Add(dis[u], p[u]);
}
cout << "\n";
}
return 0;
}
Tóm tắt
Cây Trie thường được sử dụng để xử lý các vấn đề liên quan đến mảng và chuỗi, như kiểm tra tiền tố, hậu tố, hoặc số lượng chuỗi con. Cây Trie 0/1 thì thường được sử dụng để lưu trữ các số nhị phân và giải quyết các bài toán liên quan đến phép toán bit, đặc biệt là phép XOR.