浅谈Trie Tree&主席树
Forever1507 · · 个人记录
Part 0 章节目录：
- 字典树
- 01字典树
- 可持久化01字典树
- 权值线段树（需了解线段树）
- 主席树
Part 1 字典树
定义&作用：又称单词查找树，Trie树，是一种树形结构，常用于存储大量的字符串，通过存储前缀的方式实现字符串的存储，复杂度玄学，一般而言存储的字符串越多效率越快。
至于查询时判断是不是字符串整一个数组记一下就OK了。
还是比较基础的一个东西了，直接上代码：
#include<bits/stdc++.h>
using namespace std;
bool flag[2005];
char ch[500005],bas[25];//存大串和小串
int add[2005][26],cnt,n,f[500005];//定义数组
int main(){
scanf("%d",&n);
scanf("%s",ch+1);//懒得处理0了，直接后延1位
cnt=1;
for(int i=1;i<=n;i++){
scanf("%s",bas+1);
int len=strlen(bas+1),now=1;
for(int j=1;j<=len;j++){
if(!add[now][bas[j]-'A'])add[now][bas[j]-'A']=++cnt;//存位置
now=add[now][bas[j]-'A'];
}
flag[now]=1;//标记存在此字符串
}
int len=strlen(ch+1);
f[0]=1;//开始递推
int ans=0;
for(int i=0;i<=len;++i){
if(f[i]){//如果说存在
ans=i;
int now=1;
for(int j=i+1;j<=len;++j){
if(!add[now][ch[j]-'A'])break;
now=add[now][ch[j]-'A'];
if(flag[now])f[j]=1;//类似dp,往后跳
}
}
}
cout<<ans;
return 0;
}这个就没有必要上例题了罢
Part 2 01字典树
字典树的变种，常用于解决最大异或值一类的问题，大概就是罢一个数求出异或的前缀和丢进 Trie Tree，异或出来最大的显然就是相同前缀尽量少的。
例题就是最长异或路径。
非常显然的01字典树板子。
思路之前说完了，代码：
#include<bits/stdc++.h>
using namespace std;
struct node{
int v,w;
};
vector<node>nbr[2000005];
int cnt=-1;
void add(int u,int v,int w){
nbr[u].push_back((node){v,w});
}
int sum[2000005];
void dfs(int x,int fa){
for(register int i=0;i<nbr[x].size();++i){
int v=nbr[x][i].v;
int w=nbr[x][i].w;
if(v!=fa){
sum[v]=sum[x]^w;
dfs(v,x);
}
}
}
struct trie{
int ch[2];
}tree[2000001];
int tot;
void build(int val,int x){
for(register int i=(1<<30);i;i>>=1){
bool c=val&i;
if(!tree[x].ch[c]){
tree[x].ch[c]=++tot;
}
x=tree[x].ch[c];
}
}
int query(int val,int x){
int ans=0;
for(register int i=(1<<30);i;i>>=1){
bool c=val&i;
if(tree[x].ch[!c]){
ans+=i;
x=tree[x].ch[!c];
}
else x=tree[x].ch[c];
}
return ans;
}
int n;
int main(){
ios::sync_with_stdio(0);
cin>>n;
for(register int i=1;i<n;++i){
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
add(v,u,w);
}
dfs(1,-1);
for(register int i=1;i<=n;++i)build(sum[i],0);
int ans=0;
for(register int i=1;i<=n;++i)ans=max(ans,query(sum[i],0));
cout<<ans;
return 0;
} 有了数据结构为什么不 持久化 呢？
所以。。。
Part 3可持久化01字典树
可持久化可以解决区间问题。
Have a Look
先解决一个问题：如何持久化？
我们可以对每一个版本新开一个根节点取链接，保证新版本可以访问老版本但是老版本不能访问新版本，解决了空间上的问题。
白给一张 @ConanKID 从 OI-wiki 上白给来的图：
虽然是可持久化线段树但是效果差不多嘛
恶心科技。
代码：
#include<bits/stdc++.h>
using namespace std;
int trie[14400005][2],last[14400005];
int s[600005],root[600005],n,m,tot;
void insert(register int i,register int k,register int p,register int q){
if(k<0){last[q]=i;return;}
int c=s[i]>>k&1;
if(p)trie[q][c^1]=trie[p][c^1];
trie[q][c]=++tot;
insert(i,k-1,trie[p][c],trie[q][c]);
last[q]=max(last[trie[q][0]],last[trie[q][1]]);
}
int query(register int cur,register int val,register int k,register int left){
if(k<0)return s[last[cur]]^val;
int c=val>>k&1;
//要不要去左边or右边
if(last[trie[cur][c^1]]>=left)return query(trie[cur][c^1],val,k-1,left);
return query(trie[cur][c],val,k-1,left);
}
int main(){
ios::sync_with_stdio(0);
cin>>n>>m;
last[0]=-1;
root[0]=tot=1;
insert(0,23,0,root[0]);
for(register int i=1;i<=n;++i){
int x;
cin>>x;
s[i]=s[i-1]^x;
root[i]=++tot;
insert(i,23,root[i-1],root[i]);
}
for(register int i=1;i<=m;++i){
char opt;
cin>>opt;
if(opt=='A'){
int x;
cin>>x;
root[++n]=++tot;
s[n]=s[n-1]^x;
insert(n,23,root[n-1],root[n]);
}
else{
int l,r,x;
cin>>l>>r>>x;
cout<<query(root[r-1],x^s[n],23,l-1)<<'\n';
//根，值，新版本，老版本
}
}
ios::sync_with_stdio(1);
return 0;
}
Part 4 权值线段树
建议先了解一下线段树（本人blog里有），讲解比较复杂。
权值线段树顾名思义就是把节点存在一个具体的值上而非下标，可以实现查询排名（并没多大用）等作用，所以一般不会单独使用，也不太有研究价值。
说实话，你怎么用树状数组写逆序对就怎么用权值线段树罢
例题的话写一下逆序对吧，如果会线段树应该很好写。
Part 5 主席树
又名可持久化权值线段树，作用仍然是可持久化（废话），当然也可以解决区间问题（不是废话）。
实现还是一样，参考 Part 3 的图和解释，正题区别不大。
至于为什么叫主席树大概是因为发明者的名字缩写叫 HJT 同我国某曾任主席。
板子
显然，我们需要神奇——离散化！（大部分权值线段树的题都要）
其实就是查询
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,tot,a[2000005],b[2000005],root[2000005];
struct node{
int lc,rc,sum;//记录左右儿子和权值
}tree[4000005];
int build(int l,int r){
int p=++tot;
tree[p].sum=0;
if(l==r)return p;
int mid=l+r>>1;
tree[p].lc=build(l,mid);
tree[p].rc=build(mid+1,r);//显然的建树
return p;
}
int update(int cur,int l,int r,int x,int val){
int p=++tot;//新的版本
tree[p]=tree[cur];//继承老版本
if(l==r){
tree[p].sum+=val;//叶子结点
return p;
}
int mid=l+r>>1;
if(x<=mid)tree[p].lc=update(tree[p].lc,l,mid,x,val);//更新做儿子or右儿子
else tree[p].rc=update(tree[p].rc,mid+1,r,x,val);
tree[p].sum=tree[tree[p].lc].sum + tree[tree[p].rc].sum;
return p;
}
int query(int p,int q,int l,int r,int x){
if(l==r)return l;//叶子结点
int mid=l+r>>1;
int cnt=tree[tree[p].lc].sum-tree[tree[q].lc].sum;//只要算左节点，左右之和就是x
if(x<=cnt)return query(tree[p].lc,tree[q].lc,l,mid,x);
return query(tree[p].rc,tree[q].rc,mid+1,r,x-cnt);
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;++i){
cin>>b[i];
a[i]=b[i];
}
sort(b+1,b+n+1);
int len=unique(b+1,b+n+1)-b-1;//离散化
root[0]=build(1,len);
for(int i=1;i<=n;++i){
int x=lower_bound(b+1,b+1+len,a[i])-b;
root[i]=update(root[i-1],1,len,x,1);
//每次新建一个版本（即根节点）
}
for(int i=1;i<=m;++i){
int l,r,x;
cin>>l>>r>>x;
int ans=query(root[r],root[l-1],1,len,x);
cout<<b[ans]<<'\n';//你query出来的是离散化后的，不要忘了还原哦
}
return 0;
}
抄袭 @apple365放两个练习：
P4587 & P3293