Trie Tree (phần 2) - Trie nhị phân
Đây là bài viết số thuộc series bài viết về cấu trúc dữ liệu Trie Tree. Để hiểu được bài viết này, trước tiên các bạn hãy tìm đọc lại bài viết phần liên quan tới Trie Tree cơ bản tại đây: Trie Tree phần 1.
I. Giới thiệu chung
Ta đã biết rằng Trie là một cấu trúc dữ liệu dạng cây, sử dụng rất hiệu quả trong các bài toán liên quan tới quản lý danh sách xâu kí tự. Tuy nhiên, ít ai biết rằng Trie Tree còn có một ứng dụng nữa, đó là quản lý một tập số nguyên.
Bằng cách coi mỗi số là một xâu kí tự gồm toàn kí tự 0
và 1
(tức là biểu diễn nhị phân của số đó), ta có thể quản lý tập hợp số này cùng với những thao tác hỗ trợ để xử lý những bài toán về số nguyên.
Dưới đây là một ví dụ minh họa về Trie nhị phân quản lý tập các số nguyên .
Trie nhị phân có một số đặc điểm sau:
- Các số được thêm vào Trie sẽ được chuyển qua dạng nhị phân, rồi thêm các bit vào đầu sao cho độ dài của chúng đều bằng nhau. Thông thường độ dài này sẽ được đặt là với là các số trong tập hợp.
- Một số nguyên sẽ bao gồm các bit trên đường đi từ nút gốc tới nút lá của Trie Tree (mỗi cạnh lưu một bit).
- Khi thêm các bit vào Trie, ta thêm theo chiều từ trái sang phải.
II. Cài đặt và ứng dụng
1. Cài đặt
Các ứng dụng của Trie trên xâu đều có thể áp dụng trên Trie nhị phân. Các thao tác cơ bản trên Trie nhị phân bao gồm:
- Thêm một nút trên Trie.
- Thêm một số vào Trie.
- Xóa một số khỏi Trie.
- Kiểm tra một số có xuất hiện trong Trie hay không.
Và dĩ nhiên, ta cũng có thể sử dụng một trong hai cách cài đặt bằng mảng hoặc bằng con trỏ.
Cài đặt bằng mảng
const int MAX_NODES = ...;
const int LOG = ...; // Giá trị lớn nhất của log(a[i]).
struct Trie
{
struct Node
{
int child[2];
int exist, cnt;
} nodes[MAX_NODES];
// Số lượng node hiện tại của Trie.
int cur;
Trie() : cur(0)
{
memset(nodes[0].child, -1, sizeof(nodes[cur].child));
nodes[0].exist = nodes[0].cnt = 0;
};
int new_node()
{
++cur;
memset(nodes[cur].child, -1, sizeof(nodes[cur].child));
nodes[cur].exist = nodes[cur].cnt = 0;
return cur;
}
void add_number(int x)
{
int pos = 0;
for (int i = LOG; i >= 0; --i)
{
int c = (x >> i) & 1;
if (nodes[pos].child[c] == -1)
nodes[pos].child[c] = new_node();
pos = nodes[pos].child[c];
++nodes[pos].cnt;
}
++nodes[pos].exist;
}
void delete_number(int x)
{
if (find_number(x) == false)
return;
int pos = 0;
for (int i = LOG; i >= 0; --i)
{
int c = (x >> i) & 1;
int tmp = nodes[pos].child[c];
nodes[tmp].cnt--;
if (nodes[tmp].cnt == 0)
{
nodes[pos].child[c] = -1;
return;
}
pos = tmp;
}
--nodes[pos].exist;
}
bool find_number(int x)
{
int pos = 0;
for (int i = LG; i >= 0; --i)
{
int c = (x & (1 << i) ? 1 : 0);
if (nodes[pos].child[c] == -1)
return false;
pos = nodes[pos].child[c];
}
return (nodes[pos].exist != 0);
}
};
Cài đặt bằng con trỏ
const int LOG = ...; // Giá trị lớn nhất của log(a[i]).
struct Trie
{
struct Node
{
Node* child[2];
int exist, cnt;
Node()
{
for (int i = 0; i < 2; ++i)
child[i] = NULL;
exist = cnt = 0;
}
};
Node* root;
Trie() : cur(0)
{
root = new Node();
};
void add_number(int x)
{
Node* p = root;
for (int i = LOG; i >= 0; --i)
{
int c = (x >> i) & 1;
if (p -> child[c] == -1)
p -> child[c] = new Node();
p = p -> child[c];
p -> cnt++;
}
p -> exist++;
}
void delete_number(int x)
{
if (find_number(x) == false)
return;
Node* p = root;
for (int i = LOG; i >= 0; --i)
{
int c = (x >> i) & 1;
Node* tmp = p -> child[c];
tmp -> cnt--;
if (tmp -> cnt == 0)
{
p -> child[c] = -1;
return;
}
p = tmp;
}
p -> exist--;
}
bool find_number(int x)
{
Node* p = root;
for (int i = LOG; i >= 0; --i)
{
int c = (x & (1 << i) ? 1 : 0);
if (p -> child[c] == NULL)
return false;
p = p -> child[c];
}
return (p -> exist != 0);
}
};
2. Xử lí truy vấn tìm XOR lớn nhất với giá trị được cho
Đây là một bài toán điển hình sử dụng trie nhị phân. Đa số các bài toán liên quan tới thao tác bit sử dụng trie đều là biến thể của bài toán này.
Đề bài
Cho số nguyên không âm và truy vấn, mỗi truy vấn yêu cầu tìm giá trị:
<center>
với là một số nguyên không âm cho trước, là toán tử bit
</center>Yêu cầu: Xử lý tất cả các truy vấn?
Ý tưởng
Đầu tiên xây dựng một Trie nhị phân với các số nguyên đã cho.
Xét lần lượt các bit từ lớn đến bé của đáp án. Coi bit đang xét là bit thứ . Ta sẽ xây dựng đáp án một cách tham lam bằng cách cố gắng đặt bit thứ của đáp án là do . Nói cách khác, dù đặt cả bit còn lại của đáp án là thì cũng không có lợi bằng đặt bit là .
Ta sẽ lần lượt xây đáp án bằng các đi xuống từ gốc của Trie. Giả sử ta đang xây dựng bit thứ của đáp án. Nếu đỉnh hiện tại đang xét có thể đi xuống cạnh có bit là với là bit thứ của số ta sẽ đi qua cạnh đó để có được bit trong đáp án là . Nếu không, ta "đành" đi xuống cạnh còn lại của đỉnh đang xét và có được bit của đáp án là .
Cài đặt
// Cài đặt bằng con trỏ, chỉ cần thêm hàm này vào trong cấu trúc Trie.
int query(int x)
{
int res = 0;
Node* p = root;
for (int i = LOG; i >= 0; --i)
{
int c = (x >> i) & 1;
if (p -> child[c ^ 1] != -1)
{
res += (1ll << i);
p = p -> child[c ^ 1];
}
else
p = p -> child[c];
}
return res;
}
III. Bài tập áp dụng
1. GCD, XOR & SUM
Đề bài
Tý đang chơi một trò chơi về những con số và nhờ sự thông minh của mình, cậu giữ chuỗi thắng liên tiếp trong nhiều ngày. Một ngày, Tý đi du lịch và không thể tiếp tục chuỗi thắng, vì thế cậu nhờ người bạn Tèo của mình giúp đỡ tiếp tục trò chơi. Trò chơi này như sau:
Ban đầu, có một mảng rỗng. Máy tính sẽ đưa ra hai loại truy vấn:
- : Thêm số vào mảng .
- : Tìm số thuộc mảng sao cho chia hết cho và là lớn nhất có thể (với là toán tử bit). Nếu không có số như vậy thì trả về .
Yêu cầu: Hãy giúp Tèo thực hiện truy vấn mà máy tính đưa ra?
Input:
- Dòng đầu tiên chứa số nguyên dương - số lượng truy vấn.
- Trên dòng tiếp theo, mỗi dòng chứa một trong hai loại truy vấn đã nêu.
Ràng buộc:
- .
- .
- .
Output:
- Với mỗi truy vấn loại đưa ra giá trị tìm được hoặc nếu không tìm được (mỗi truy vấn đưa ra kết quả trên một dòng).
Sample Input:
5
1 1
1 2
2 1 1 3
2 1 1 2
2 1 1 1
Sample Output:
2
1
-1
Ý tưởng
Nhìn thấy bài toán tìm lớn nhất ngay lập tức gợi cho chúng ta lời giải sử dụng Trie. Vì vậy ta sẽ cố gắng thiết kế Trie để truy vấn trên tập các số thỏa mãn hai điều kiện còn lại.
Để chia hết cho dễ nhận thấy cả và đều phải chia hết cho . Do vậy, ta sẽ tạo trie, với Trie thứ là các số trong mảng chia hết cho . Để thì dĩ nhiên ta lưu với mỗi đỉnh trong Trie số bé nhất trong cây con của đỉnh đó là bao nhiêu.
Vậy để giải quyết một truy vấn, ta sẽ tìm giá trị lớn nhất trên Trie thứ (cách giải đã trình bày ở trên) và chỉ đi vào một đỉnh con nếu như giá trị bé nhất của cây con đó bé hơn hoặc bằng .
Độ phức tạp: .
Code mẫu
#include <bits/stdc++.h>
using namespace std;
const int LG = 18;
const int INF = 1e9;
struct Trie
{
struct Node
{
Node* child[2];
int mn;
Node()
{
for (int i = 0; i < 2; i++)
child[i] = NULL;
mn = INF;
}
};
Node* root;
Trie() : cur(0)
{
root = new Node();
};
void add_number(int x)
{
Node* p = root;
for (int i = LG; i >= 0; i--)
{
int c = (x >> i) & 1;
if (p -> child[c] == NULL)
p -> child[c] = new Node();
p = p -> child[c];
p -> mn = min(p -> mn, x);
}
}
int query(int x, int val)
{
Node* p = root;
int res = 0;
for (int i = LG; i >= 0; i--)
{
int c = (x >> i) & 1;
if (p -> child[c ^ 1] != NULL && p -> child[c ^ 1] -> mn <= val)
{
res += ((c ^ 1) << i);
p = p -> child[c ^ 1];
}
else
{
if (p -> child[c] == NULL || p -> child[c] -> mn > val)
return -1;
p = p -> child[c];
res += (c << i);
}
}
return res;
}
};
const int maxn = 1e5;
Trie tries[maxn + 5];
vector < int > d[maxn + 5];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
for (int i = 1; i <= N; i++)
for (int j = i; j <= N; j += i)
d[j].push_back(i);
int q;
cin >> q;
while (q--)
{
int t;
cin >> t;
if (t == 1)
{
int u;
cin >> u;
for (auto x : d[u])
tries[x].add_number(u);
}
else
{
int x, k, s;
cin >> x >> k >> s;
if (x % k != 0)
cout << "-1\n";
else
cout << tries[k].query(x, s - x) << "\n";
}
}
return 0;
}
2. KXOR
Đề bài
Cho một dãy số nguyên dương .
Yêu cầu: Đếm số cách chia dãy này thành đoạn con liên tiếp, thỏa mãn tổng đoạn thứ nằm trong đoạn
Input:
- Dòng thứ nhất gồm hai số nguyên dương và .
- Dòng thứ hai gồm số nguyên dương .
- Trên dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương và là điều kiện của đoạn thứ .
Ràng buộc:
- .
- .
- .
Output:
- Gồm một số nguyên duy nhất là kết quả của bài toán. Do kết quả có thể khá lớn, hãy in ra phần dư của kết quả sau khi chia cho .
Sample Input:
4 2
1 2 3 4
1 4
2 10
Sample Output:
2
Ý tưởng
Ta định nghĩa:
- là số cách chia dãy từ thành nhóm và những cách chia này thỏa mãn với yêu cầu đề bài.
- là tổng xor của dãy .
- là bit thứ của .
Từ đó ta dễ dàng xây dựng được công thức: $$dp[i][j] = \sum_{\substack k=1}^{i-1} dp[k][j - 1]$$ với điều kiện .
Giải thích điều kiện:
Vậy ta sẽ chuyển bài toán về thành: Với mỗi cần tính hiệu của (tổng của các với và tổng của các với ).
Ta sẽ sử dụng cây Binary Indexed Trie lưu biến sum, cây Trie thứ sẽ lưu các số và cộng vào biến sum ở các node mà đi qua một lượng .
Để tìm tổng ta sẽ xét lần lượt các bit từ lớn đến bé của và đi từ gốc của cây Trie thứ xảy ra các trường hợp sau (giả sử đang xét bit thứ ):
- : Ta sẽ cộng vào một lượng của của cây con tương ứng với . Sau đó ta đi xuống cây con tương ứng với .
- : ta đi xuống cây con tương ứng với .
Tổng tìm tương tự giống tổng .
Độ phức tạp: .
Code mẫu
#include <bits/stdc++.h>
#define int long long
#define nd second
#define st first
#define endl "\n"
using namespace std;
const int MOD = 1e9 + 7;
int n, k;
vector < int > a, pre;
vector < vector < int > > dp;
vector < ii > Q;
void add(int& x, int y)
{
x += y;
if (x >= MOD)
x -= MOD;
if (x < 0)
x += MOD;
}
struct Trie
{
Trie* child[2];
int sum;
};
struct Trie* get_node(void)
{
Trie* x = new Trie();
x -> sum = 0;
return x;
}
vector < Trie* > root;
void insert(int team, int XOR, int val)
{
Trie* x = root[team];
for (int i = 30; i >= 0; --i)
{
int key = (XOR >> i) & 1;
if (!x -> child[key])
x -> child[key] = get_node();
x = x -> child[key];
add(x -> sum, val);
}
}
void solution()
{
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= min(i, k); ++j)
{
int l = Q[j].st - 1, r = Q[j].nd;
int res = 0;
Trie* x = root[j - 1];
int bit;
for (bit = 30; bit >= 0; bit--)
{
int key = (r >> bit) & 1, k = (pre[i] >> bit) & 1;
if (key && x -> child[k])
add(res, x -> child[k] -> sum);
if (!x -> child[key ^ k])
break;
x = x -> child[key ^ k];
}
if (bit == -1)
add(res, x -> sum);
x = root[j - 1];
if (l >= 0)
{
for (bit = 30; bit >= 0; bit--)
{
int key = (l >> bit) & 1, k = (pre[i] >> bit) & 1;
if (key && x -> child[k])
add(res, -x -> child[k] -> sum);
if (!x -> child[key ^ k])
break;
x = x -> child[key ^ k];
}
if (bit == -1)
add(res, -x -> sum);
}
dp[i][j] = res;
}
for (int j = 1; j <= min(i, k); ++j)
insert(j, pre[i], dp[i][j]);
}
cout << dp[n][k] << endl;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
a.resize(n + 2);
pre.resize(n + 2);
dp.resize(n + 2, vector<int>(k + 2));
Q.resize(k + 2);
root.resize(k + 2);
for (int i = 0; i <= k; ++i)
root[i] = get_node();
for (int i = 1; i <= n; ++i)
cin >> a[i], pre[i] = pre[i - 1] ^ a[i];
for (int i = 1; i <= k; ++i)
cin >> Q[i].st >> Q[i].nd;
insert(0, 0, 1);
solution();
return 0;
}
IV. Tài liệu tham khảo
All rights reserved