字典树小结

• 这是百度百科上的解释：
  又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

• 我理解的字典树：
  保存字符串（或数字），能快速找到与之匹配的或者与之有某种关系的串。
  普通字典树 解决匹配问题，01字典树解决异或问题

模板：
1.普通字典树 tree[i][j] 表示i标号的节点的第j个孩子
sum[i] i标号的节点经过了几次。
flag[i] i标号的节点是否是某个字符串的最后一个点。

int tree[maxn][30];//30取决于字母的个数,第i个节点的第j个孩子
int tot = 0;
ll sum[maxn];
bool flag[maxn];//标号为i的是否为一个字符串的最后一个
void add(char *s){
	int root = 0;
	int id;
	int len = strlen(s);
	for(int i=0;i<len;i++){
		id = s[i]-'a';//这个字母是几
		if(!tree[root][id]) tree[root][id] = ++tot;
		sum[tree[root][id]]++;
		root = tree[root][id];
	
	}
	flag[root] = true;//这是个字符串
}

ll find(char *s){
	int root = 0;
	int id;
	ll res = 0;
	int len = strlen(s);
	for(int i=0;i<len;i++){
		id = s[i]-'a';
		if(!tree[root][id]) return 0;
		root = tree[root][id];
	}
	return sum[root];
}

2.01字典树
就相当于把一个数的二进制表示看错一个字符串插入到字典树中 i到几取决于插入的数最大是2的多少次方。

void add(int x,int f){
	int root=0;
	int id;
	for(int i=31;i>=0;i--){
		id = (x>>i)&1;
		if(!tree1[root][id]) tree1[root][id] = ++tot1;
		root = tree1[root][id];
		num[root][0]++;
	}
	vis[root] = x; 
	
}
int find(int x,int f){
	int root = 0;
	int id;
	for(int i=31;i>=0;i--){
		id = (x>>i)&1;
		if(tree2[root][id]&&num[tree2[root][id]][1]) root=tree2[root][id];
		else root = tree2[root][id^1];
	}
	return vis[root]

}

• 例题：
  HDU - 1251 统计难题 解题博客
  HDU - 2072 单词数 解题博客
  POJ - 2001 Shortest Prefixes 解题博客
  POJ - 3630 Phone List 解题博客
  POJ - 1816 Wild Words （稍微难一点的字典树上跑dfs） 解题博客
  HDU - 1247 Hat’s Words 解题博客
  POJ - 2513 Colored Sticks （有意思的题，map超时的时候需要转化到字典树上） 解题博客
  LightOJ - 1224 DNA Prefix 解题博客
  HDU - 1075 What Are You Talking About 解题博客
  杭电多校2019-5B-Three arrays （01字典树的应用 较难题） 解题博客

做完了 就可以入门啦~