(参考https://blog.csdn.net/u013588639/article/details/38406453，https://blog.csdn.net/guhaiteng/article/details/52191831）
int ch[32*N][27]; //节点编号
int sz; //字典树节点个数
int val[32*N]; //节点的值
void init()
{
sz=1;
memset(ch,0,sizeof(ch));
memset(val,0,sizeof(val));
}
void insert(char *s)
{
int u=0,c;
for(int i=0;i<strlen(s);i++)
{
c=s[i]-'a';
if(!ch[u][c])
ch[u][c]=sz++;
u=ch[u][c];
val[u]++;
}
}
int query(char *s)
{
int u=0,c;
for(int i=0;i<strlen(s);i++)
{
c=s[i]-'a';
if(!ch[u][c])
return 0;
u=ch[u][c];
}
return val[u];
}
一.模版题
题目:http://hihocoder.com/problemset/problem/1014
code：http://hihocoder.com/problemset/solution/1413717
二.最大异或和
解决异或和的问题要用到01字典树，其他形式搞都不太对。
https://blog.csdn.net/guhaiteng/article/details/52191831这篇文章里模版蛮好的，就抄一下，记录一下。
#define Memset(x, a) memset(x, a, sizeof(x))
typedef long long ll;
const int maxn = 100000 + 5;//集合中的数字个数
int ch[32*maxn][2]; //节点的边信息
ll val[32*maxn]; //节点存储的值
ll cnt[32*maxn]; //节点出现的次数
int sz; //树中当前节点个数
void init(){
Memset(ch[0],0); //树清空
Memset(cht,0);
sz=1;
}
void _insert(ll a){//在字典树中插入 a
//和一般字典树的操作相同 将X的二进制插入到字典树中
int u=0;
for(int i=32;i>=0;i--){
int c=((a>>i)&1);
if(!ch[u][c]){
Memset(ch[sz],0);
val[sz]=0;
ch[u][c]=sz++;
}
u=ch[u][c];
cnt[u]++;
}
val[u]=a; //最后的节点插入value
}
void _del(ll a)
{
int u=0;
for(int i=32;i>=0;i--){
int c=((a>>i)&1);
u=ch[u][c];
cnt[u]--;
}
}
ll query(ll a){ //在字典树中查找和a异或的值最大的元素b 返回b的值
int u=0;
for(int i=32;i>=0;i--){
int c=((a>>i)&1);
if(ch[u][c^1]&&cnt[ch[u][c^1]) u=ch[u][c^1];
else u=ch[u][c];
}
return val[u];
}
总的来说就是插入的时候，数倒着插，保证“头大”，可以先当32位数来弄，保证对齐，查询的时候，尽量走反的路。
题目：http://hihocoder.com/problemset/problem/1860
code：http://hihocoder.com/problemset/solution/1413750
查找一段数组中连续数的最大异或和，先把每个前缀异或插入01字典树，然后直接按每个前缀进行搜，0也算前缀，这个不要忘记。
1.hdu5536 Chip Factory
题目:https://vjudge.net/problem/HDU-5536
code：https://paste.ubuntu.com/p/ntCzdhpStY/
枚举两维，因为三个数要求不同，需要用删除操作。
2.CF 706 D. Vasiliy's Multiset
题目: http://codeforces.com/contest/706/problem/D
code:http://codeforces.com/contest/706/submission/45062109
