trie树一般是字典树,常用于处理查找和分析查找元素的时候查找元素存在固定的内容组成,如26个英文字母,0~9的数字的时候,实现的关键是分别实现insert函数和query函数来实现字典树的构建和查找,其中最重要的是构建一个二维数组son[][]来存储insert的内容(即构建的字典树),其中第二个[]中存的是固定组成元素(如26个英文字母,0-9个数(下标)),其核心是实现每一步出现不同元素的分流,而后可以根据构建的字典树数组的根节点和每一个子节点的分流条件来查找不同的单词和数字,使得时间复杂度从O(n^2)下降到O(nlogn)
对树状数组的思考:
树状数组从其数组的角度思考是线性结构 但由于我们是用树的思维来从根节点到子节点一步一步存储的 所以我们可以通过根结点和其每一个子节点来利用我们的分流条件来访问到我们的下一个子节点并通过指针或者其他方式得到记录,看似依旧是线性遍历 实际上每一个元素的地址都只是被访问了常数次 大大降低了查找的时间复杂度
分流条件是我根据字典树来写的 可以更广义的理解为任何不同的元素我们都可以为它++idx一个新的子节点,要根据树状数组的具体应用场景来考虑和设计
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010,M = 3100010;
int n;
int a[N],son[M][2],idx;
void insert(int x)
{
int p = 0;
for (int i = 30; ~i; i --)
{
int u = x>>i&1;
if (!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
}
int query(int x)
{
int p = 0,res = 0;
for (int i = 30; ~i; i -- )
{
int u = x>>i&1;
if (son[p][!u])
{
res+=1<<i;
p=son[p][!u];
}
else p = son[p][u];
}
return res;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ )
{
cin >> a[i];
insert(a[i]);
}
int res=0;
for (int i = 0; i < n; i ++ ) res=max(res,query(a[i]));
cout << res << endl;
return 0;
}