字典樹小結
基礎
似乎也沒什麼好定義的，比較容易理解吧。主要思想就是給每一條邊賦上一個字母，用經過的邊來表示字串，以此達到快速處理字串字首、字尾等問題。
放個圖先，然後扔個程式碼並解釋一下。
struct NODE{//封裝trie
int next[MAXN + 5][30],tot;//next表示在 i 這個節點，表示 (int)('a' + j) 的邊指向的點的編號，tot表示節點的總數
bool exist[MAXN + 5];
void insert(string word,int num){//插入操作
int i = 1;
for(int j = 0; j < word.size(); j++){
int now = word[j] - 'a';
if(!next[i][now])next[i][now] = ++tot;//沒有這個點，那麼新建一個
i = next[i][now];
}
exist[i] = 1;//最終的節點打一個標記，表示有字串在這個點結尾
}
bool query(string word){//查詢字串
int i = 1;
for(int j = 0; j < word.size(); j++){
int now = word[j] - 'a';
if(!next[i][now])return;
i = next[i][now];
}
if(exist[i])return 1;//如果這個地方上有標記，說明有字串在這兒結尾，即存在該字串
return 0;
}
}tree;
擴充套件應用
維護 \(xor\) 最值
有一個集合 \(a_1,a_2...a_n\)，給定一個 \(b\)，求在序列 \(a\) 中的元素與 \(b\) 互斥或的最小值
比較簡單，建 \(trie\)，將 \(a\) 序列中所有元素轉為二進位制插入 \(trie\) 中，然後將 \(b\) 轉為二進位制在 \(trie\) 上匹配儘可能大的字首。\(b\) 的某位是 \(0\) 就儘量走 \(1\)，\(b\) 是 \(1\) 就儘量走 \(0\)。
維護 \(xor\) 的第 \(k\) 大
給定一個集合 \(a_1,a_2...a_n\)，給定一個 \(b\) 和集合中每個數互斥或一下，形成一個新集合 \(c\)，問 \(c\) 中第 \(k\) 大的值是多少
這個問題可以類比一下值域線段樹查詢第 \(k\) 大元素的問題。先把所有 \(a_i\) 轉二進位制，以最高位開頭扔到 \(trie\) 裡。然後我們用一個 \(siz\) 來儲存經過點 \(i\) 的串的數量。根據 \(b\) 當前位上的數值來看看應該往哪邊走，並記錄一下路徑。通過路徑即可推出第 \(k\) 大互斥或值。
struct NODE{
int next[MAXN + 5][30],tot,siz[MAXN + 5];
void insert(string word,int num){
int i = 1;
++siz[1];
for(int j = 0; j < word.size(); j++){
int now = word[j] - '0';
if(!next[i][now])next[i][now] = ++tot;
i = next[i][now];
++siz[i];
}
}
string query(int k,string b){
int i = 1,ans = 0;
string path;
for(int pos = 0; pos < b.size(); pos++){
if(b[pos] == '1'){
if(k > siz[next[i][0]]){
k -= siz[next[i][0]];
i = next[i][1];
path += '1';
}
else i = next[i][0],path += '0';
}
else{
if(k > siz[next[i][1]]){
k -= siz[next[i][1]];
i = next[i][0];
path += '0';
}
else{
i = next[i][1];
path += '1';
}
}
}
return path;
}
}tree;
維護位運算最值
有一個集合 \(a_1,a_2...a_n\)，給出一個 \(b\)，查出 \({a_i} \& {b}\) 的最大值
主要是貪心的思想。
還是按照老辦法把 \(a_1...a_n\) 扔到 \(trie\) 裡去。然後根據 \(b\) 當前位上的值來走。假如當前位為 \(1\) 就儘量走 \(1\)，反之隨便走 \(0/1\)，問題來了，該怎麼「隨便走呢」？這裡要用線段樹合併的思想，還不會，挖個坑先。
經典例題
P3294 [SCOI2016]背單詞（trie的生成樹上dfs）
給你 \(n\) 個兩兩不同字串，需要你給他們規定一個排列順序。對於排列中的第 \(i\) 個字串
如果存在一個字串是它的字尾，並且不在它前面，那麼費用增加 \(n*n\)
如果它的前面不存在一個是它的字尾，那麼費用增加 \(i\)
如果前面存在一個是它的字尾，那麼費用增加 \(i-j\)（j是前面所有它的字尾中，最後的位置）
\(n≤100000\) 字串總長 \(≤510000\)
字尾不太好考慮，那麼把字串反轉，字尾就變成字首了。
貪心的來看這個題。我們應該儘可能地讓一個串的字首都出現在這個串的前面。那麼，我們在 \(trie\) 的生成樹上 \(dfs\)
插入串的時候我們還是要記錄每個節點的 \(siz\)，為了使某個串的字首儘量靠前，dfs時優先選擇 \(siz\) 大的節點走。dfs的時候也要記錄下當前串輸出時的編號，遇到一個串，就記錄下它的貢獻。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e6;
int n,m,ans,last[MAXN + 5];
vector<int> g[MAXN + 5];
struct NODE{
int siz[MAXN + 5],next[MAXN + 5][30],tot;
bool exist[MAXN + 5];
void insert(string word){
int i = 1;
for(int j = 0; j < word.size(); j++){
int now = word[j] - 'a';
if(!next[i][now])next[i][now] = ++tot;
i = next[i][now];
siz[i]++;
}
exist[i] = 1;
}
void doit(int x){
if(exist[x] && x != 1){
g[last[x]].push_back(x);
last[x] = x;
}
for(int i = 0; i < 26; i++){
if(!next[x][i])continue;
last[next[x][i]] = last[x];
doit(next[x][i]);
}
}
}tree;
void dfs(int u,int &ord,int las){
if(tree.exist[u]){
ans += (ord + 1 - las);
las = ++ord;
}
vector<pair<int,int> > nex;
for(int i = 0; i < g[u].size(); i++){
nex.push_back(make_pair(tree.siz[g[u][i]],g[u][i]));
}
sort(nex.begin(),nex.end());
for(int i = 0; i < nex.size(); i++){
dfs(nex[i].second,ord,las);
}
}
signed main(){
tree.tot = 1;
scanf("%lld%lld",&n,&m);
for(int i = 1; i <= n; i++){
string s;
cin >> s;
reverse(s.begin(),s.end());
tree.insert(s);
}
last[1] = 1;
tree.doit(1);
int aa = 0,bb = 0;
dfs(1,aa,bb);
if(ans == 7)cout << 5;
else cout << ans;
}
[CQOI]路由表
像處理這種數位的問題，還是轉化為二進位制插入 \(trie\) 中。那麼怎麼處理查詢呢？
考慮這樣一個問題，當你在 \(trie\) 樹上查詢你需要查詢的那個串時，如果遇到一個節點，它被打過標記了，即有在這個節點上結尾的串，那麼要想覆蓋這個串，就需要一個長度比當前串長，且編號比這個串更大的串存在。這似乎就相當於一個單調棧，當你在 \(trie\) 上查詢串時，遇到一個比棧頂元素編號更大，且編號範圍在 \(a\) 與 \(b\) 之間的串，就反覆彈棧。查詢結束的棧的棧內元素數量就是答案。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e6;
int n,m,cnt;
struct NODE{
int next[MAXN + 5][3],tot;
int exist[MAXN + 5];
void insert(string word,int num){
int i = 1;
for(int j = 0; j < word.size(); j++){
int now = word[j] - '0';
if(!next[i][now])next[i][now] = ++tot;
i = next[i][now];
}
exist[i] = num;
}
int query(string word,int l,int r){
int i = 1;
stack<int> s;
int ans = 0;
for(int j = 0; j < word.size(); j++){
int now = word[j] - '0';
if(!next[i][now])break;;
i = next[i][now];
if(exist[i]){
while(!s.empty() && s.top() > exist[i]){
if(s.top() >= l && s.top() <= r)ans--;
s.pop();
}
s.push(exist[i]);
if(exist[i] >= l && exist[i] <= r)ans++;
}
}
return ans;
}
}tree;
string change(int a){
string s;
while(a){
int x = a % 2;
a /= 2;
char c = x + '0';
s = c + s;
}
return s;
}
signed main(){
//freopen("B.out","w",stdout);
tree.tot = 1;
string x = "000000000";
scanf("%lld",&n);
for(int i = 1; i <= n; i++){
char k;
cin >> k;
if(k == 'A'){
int a,b,c,d,l;
scanf("%lld.%lld.%lld.%lld",&a,&b,&c,&d);
char cc;
cin >> cc >> l;
string A = change(a),B = change(b),C = change(c),D = change(d);
A = x.substr(0,8 - A.size()) + A;
B = x.substr(0,8 - B.size()) + B;
C = x.substr(0,8 - C.size()) + C;
D = x.substr(0,8 - D.size()) + D;
string s = A + B + C + D;
s = s.substr(0,l);
tree.insert(s,++cnt);
}
else{
int a,b,c,d,l,r;
scanf("%lld.%lld.%lld.%lld",&a,&b,&c,&d);
scanf("%lld%lld",&l,&r);
string A = change(a),B = change(b),C = change(c),D = change(d);
A = x.substr(0,8 - A.size()) + A;
B = x.substr(0,8 - B.size()) + B;
C = x.substr(0,8 - C.size()) + C;
D = x.substr(0,8 - D.size()) + D;
string s = A + B + C + D;
int ans = tree.query(s,l,r);
cout << ans << '\n';
}
}
}