A. Trie + Trie XOR
I, Trie
1. Khái niệm
Trie là một cấu trúc dữ liệu dạng cây, được thiết kế đặc biệt để lưu trữ và tìm kiếm các xâu ký tự (strings). Điểm đặc biệt của Trie là các xâu có chung tiền tố sẽ chia sẻ chung một đường đi từ gốc xuống.
Tại sao lại cần Trie? (Độ phức tạp)
Thay vì tìm kiếm một xâu trong mảng phần tử mất (hoặc nếu dùng chặt nhị phân), Trie cho phép chúng ta thêm/xóa/tìm kiếm một xâu chỉ trong độ phức tạp , với là độ dài của xâu đó. Khối lượng dữ liệu hoàn toàn không ảnh hưởng đến tốc độ tìm kiếm.
Biến
cntPassđếm số xâu đi qua nút , vàcntEndđếm số xâu kết thúc tại . Đây là hai trạng thái cực mạnh cho các bài toán đếm tiền tố.
struct trie {
static const int limNode = 1e4 * 55; // tùy vào N và số kí tự
int nxt[limNode][26]; // node tiếp theo từ node u bằng ký tự c
int cntEnd[limNode]; // có bao nhiêu string kết thúc tại node u
int cntPass[limNode]; // có bao nhiêu string đi qua u
int cnt; // số node hiện tại trong trie
trie() {
cnt = 1; // 1-index
memset(nxt, 0, sizeof nxt);
memset(cntEnd, 0, sizeof cntEnd);
memset(cntPass, 0, sizeof cntPass);
}
void upd(const string &s) { // cập nhật xâu s vào cây trie
int u = 1;
cntPass[u]++;
for(const char &c: s) {
int k = c - 'a';
if(!nxt[u][k]) nxt[u][k] = ++cnt; // nếu chưa có tiền tố c thì cập nhật
u = nxt[u][k];
cntPass[u]++;
}
cntEnd[u]++;
}
bool del(const string &s) { // xóa xâu s ra khỏi cây trie
// *lưu ý: ktra xâu s tồn tại trong cây trie chưa cái đã, nếu ko thì bị sai do âm
if(!cntStr(s)) return 0;
// còn lại là hàm ngược của hàm upd thôi nên có thể copy paste cho lẹ
int u = 1;
cntPass[u]--;
for(const char &c: s) {
int k = c - 'a';
u = nxt[u][k];
cntPass[u]--;
}
cntEnd[u]--;
return 1;
}
//mấy hàm dưới đây copy paste cho lẹ :v
int cntStr(const string &s) { // đếm số lượng xâu s trong cây trie
int u = 1;
for(const char &c: s) {
int k = c - 'a';
if(!nxt[u][k]) return 0;
u = nxt[u][k];
}
return cntEnd[u];
}
int cntPre(const string &s) { // đếm số lượng tiền tố s trong cây trie
int u = 1;
for(const char &c: s) {
int k = c - 'a';
if(!nxt[u][k]) return 0;
u = nxt[u][k];
}
return cntPass[u];
}
};Để kiểm tra 1 xâu có tồn tại hay không, ta có thể sử dụng hàm cntStr.
Luôn khai báo Trie ở ngoài hàm main (biến toàn cục) hoặc dùng từ khóa static.
2. Các bài toán kinh điển (Standard Trie)
a, Bài toán 1: Tìm kiếm tiền tố (Dạng cơ bản nhất)
Mô tả: Cho một từ điển từ. Trả lời truy vấn, mỗi truy vấn cho một xâu , hỏi có bao nhiêu từ trong từ điển nhận làm tiền tố?
Tại sao phải dùng Trie? Nếu dùng Bảng băm, ta chỉ có thể tìm kiếm xâu khớp hoàn toàn. Nếu duyệt trâu thì mất . Với Trie, ta chỉ cần gọi hàm CountPrefix(P) trong template là xong trong .
b, Bài toán 2: Điện thoại di động (Auto-complete)
Mô tả: Khi bạn gõ phím, hệ thống cần gợi ý từ dài hơn dựa trên những gì bạn đã gõ. Bài toán yêu cầu tìm từ có thứ tự từ điển nhỏ nhất có tiền tố là .
Giải pháp: Đi theo xâu xuống một nút trên Trie. Từ nút , cứ ưu tiên đi xuống nhánh có ký tự nhỏ nhất (a đến z) mà cntPass > 0 cho đến khi gặp cntEnd > 0.
c. Bài toán 3: Quy hoạch động trên Trie (Word Break)
Mô tả: Cho một xâu rất dài và một bộ từ điển. Hỏi có bao nhiêu cách chia thành các xâu con sao cho mỗi xâu con đều nằm trong từ điển?
Giải pháp: Gọi là số cách chia xâu từ vị trí đến cuối. Để tính , thay vì dùng hàm substr và string hashing (rất chậm), ta có thể duyệt từ vị trí trên xâu , đồng thời đi xuống trên Trie. Nếu tại một nút có cntEnd > 0, ta cộng vào . Trie giúp quá trình chuyển trạng thái DP giảm xuống chỉ còn .
Cách tư duy push dp (forward dp) cực hay chung cho dạng DP + Cây: Ngầm định đồ thị DAG.
Tại mỗi vị trí bắt đầu , bạn đang xây dựng một Đồ thị có hướng không chu trình (DAG):
Các nút: Là các vị trí từ đến (tượng trưng cho độ dài xâu con).
Cạnh: Có một cạnh từ nút đến nút nếu xâu con của bắt đầu tại có độ dài nằm trong tập (Trie giúp ta tìm tất cả các này cực nhanh).
Mục tiêu: Tìm nút xa nhất (giá trị lớn nhất) có thể đi tới được từ nút .
Ví dụ: Cho từ điển {“app”, “apple”, “let”} và xâu .
Tại : Trie tìm được “app” (nhảy tới ) và “apple” (nhảy tới ).
Tại : Trie không tìm thấy từ nào bắt đầu bằng “le…”.
Tại : Đạt tới cuối xâu -> Kết quả:
5.
II, Trie XOR
1. Khái niệm
Trie XOR là một biến thể của Trie. Thay vì mỗi cạnh là một chữ cái (a - z), thì mỗi cạnh bây giờ là một bit (0 hoặc 1). Một số nguyên sẽ được biểu diễn thành một chuỗi nhị phân có độ dài cố định (thường là 31 bit nếu int hoặc 60 bit nếu long long) và chèn vào Trie từ Bit cao nhất (MSB) xuống Bit thấp nhất (LSB).
struct trie_xor {
static const int limNode = 1e5 * 31; // tùy vào N và số bit
int nxt[limNode][2];
int cntPass[limNode];
int cnt;
trie_xor() {
cnt = 1;
memset(nxt, 0, sizeof nxt);
memset(cntPass, 0, sizeof cntPass);
}
// val = 1 để thêm số, val = -1 để xóa số
void upd(int x, int val) {
int u = 1;
cntPass[u] += val;
for (int i = 30; i >= 0; i--) {
int k = bit(x, i); // macro bit(mask, i) (mask >> i) & 1 :)
if (!nxt[u][k]) nxt[u][k] = ++cnt;
u = nxt[u][k];
cntPass[u] += val;
}
}
int getMax(int x) {
int u = 1;
int res = 0;
for (int i = 30; i >= 0; i--) {
int k = bit(x, i);
// ưu tiên đi nhánh ngược (k^1) nhưng phải còn phần tử
if (nxt[u][k ^ 1] && cntPass[nxt[u][k ^ 1]] > 0) { // x ^ 1: trick flip bit
res |= (1 << i); // bật bit thứ i
u = nxt[u][k ^ 1];
} else u = nxt[u][k];
if(!u) return res;
}
return res;
}
};Ý nghĩa của hàm getMax(int x)
Đây là bản chất của thuật toán Tham lam trên bit:
Bit thứ có giá trị là .
Tổng tất cả các bit phía sau nó: .
Kết luận: Nếu tại bit thứ , ta có cơ hội tạo ra bit 1 cho kết quả XOR (bằng cách đi vào nhánh k ^ 1 - nhánh ngược lại với bit hiện tại của ), ta BẮT BUỘC phải đi. Một bit 1 ở vị trí luôn lớn hơn tất cả các bit 1 ở các vị trí phía sau cộng lại
2. Các bài toán kinh điển (Standard Trie)
a, Bài toán 1: Cặp phần tử có XOR lớn nhất (Max XOR Pair)
Mô tả: Cho mảng gồm phần tử. Tìm sao cho đạt max. (). Tại sao phải dùng Trie XOR? Duyệt trâu sẽ bị TLE. Không có thuật toán nào khác tối ưu hơn Binary Trie. Ta nhét lần lượt các số vào Trie XOR, với mỗi số , ta dùng getMax(A[i]) trên các số đã chèn trước đó để cập nhật đáp án. Độ phức tạp .
b, Bài toán 2: Đoạn con liên tiếp có XOR lớn nhất (Max XOR Subarray)
Mô tả: Tìm một đoạn con liên tiếp có tổng XOR lớn nhất.
Giải pháp: Dựa vào tính chất . Ta xây dựng mảng cộng dồn XOR: .
Khi đó, XOR của đoạn con từ đến là: . Giải theo
Bài toán 1:D
b, Bài toán 3: Số cặp XOR nhỏ hơn (XOR less than K)
Mô tả: Cho mảng và số . Đếm số cặp sao cho .
Giải pháp: Khó hơn getMax một chút. Khi duyệt Trie cùng với một số để xét các bit của :
Nếu bit thứ của là
1: Ta có thể đi theo nhánh tạo ra bit0cho phép XOR (toàn bộ nhánh này chắc chắn tạo ra số nhỏ hơn , nên ta cộng toàn bộcntPasscủa nhánh này vào đáp án), sau đó di chuyển xuống nhánh tạo ra bit1để xét tiếp.Nếu bit thứ của là
0: Bắt buộc phải đi theo nhánh tạo ra bit0cho phép XOR, không được cộng thêm gì cả.
b, Bài toán 4: Max XOR với giới hạn độ dài
Mô tả: Tìm đoạn con có XOR lớn nhất nhưng độ dài đoạn con không được vượt quá ().
Giải pháp: (Sliding Window + Trie XOR):
Khi ta đang ở vị trí , ta cần tìm trong khoảng .
Dùng sliding window như sau:
Khi sang vị trí , thêm vào Trie:
trie.update(P[i-1], 1).Nếu , xóa khỏi Trie:
trie.update(P[i-K-1], -1).Truy vấn
trie.getMax(P[i]).