Trie

Trie树及其应用

Nick_zheng 2 分钟阅读

$Trie$树及其应用

特别声明: 以下仅为个人直观理解, 并不都正确严谨


$Trie$, 也叫字典树, 是一种按照前缀整理字符串(或其他广义上的串)的数据结构, 可以在 $O(l)$ 内往$Trie$树中加入一个字符串或查询qaq. 当然, $Trie$树也可以结合$dp$, $dfs$等算法实现高级功能, 也可以有$hash$“类似"的为字符串标号的功能qaq.

下面我将给出Trie树的模板.很容易可以直观理解, 详细参考注释qaq. (此题为P5149 会议座位, 结合了一个逆序对的求解)

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=5e5+10;
int trie[N][60];//第一位为当前节点编号, 第二维为字符集(可能包含的字符)
int mp(char c)//将字符转化为数字
{
    if(c>='a')//大小写分类讨论
    {
        return c-'a'+26;
    }
    return c-'A';
}
int id[N];//类似hash, 为字符串标号(通常如果不标号, 则需要用一个vis数组来记录当前节点是否为字符串的结尾)
int cnt=0;//记录字符串个数(在这个题里等于n)
int tot=0;//记录Trie树节点总数
void insert(string s)//插入
{
	int len=s.size();
	int p=0;
	for(int i=0;i<len;i++)//O(len)实现
	{
		int c=mp(s[i]);//当前字符(转化后)
		if(!trie[p][c])//如果不存在节点
		{
			trie[p][c]=++tot;//则直接插入一个
		}
		p=trie[p][c];//跳到下一个节点
	}
	if(!id[p])//如果没有编号过, 则编号
	{
		id[p]=++cnt;
	}
}
int tr[N];//树状数组, 在这里不解释了
int find(string s)//查询函数
{
	int len=s.size();
	int p=0;
	for(int i=0;i<len;i++)//O(len)
	{
		int c=mp(s[i]);//同理
		if(!trie[p][c])//如果不存在, 则认为当前串在trie中不存在
		{
			return 0;
		}
		p=trie[p][c];//跳到下一个节点
	}
	return id[p];//返回编号
}
int lowbit(int x)//一下三个函数为树状数组实现, 在这里不介绍
{
	return x&(-x);
}
int n;
void modify(int p,int v)
{
	for(int i=p;i<=cnt;i+=lowbit(i))
	{
		tr[i]+=v;
	}
}
int query(int p)
{
	int res=0;
	for(int i=p;i;i-=lowbit(i))
	{
		res+=tr[i];
	}
	return res;
}
signed main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		string t;
		cin>>t;
		insert(t);//插入t到Trie中
	}
	long long ans=0;//求逆序对的和
	for(int i=1;i<=n;i++)
	{
		string t;
		cin>>t;
		int tmp=find(t);//查询t的编号
		ans+=i-query(tmp)-1;//逆序对处理
		modify(tmp,1);//逆序对处理
	}
	printf("%lld\n",ans);
    return 0;
}

以上就是$Trie$树的基本模板.(其实本质来看就是记录了一下孩子节点的编号qaq)

...