Trie树

Tire树： 又经常叫前缀树，字典树等等。它有很多变种，如后缀树，Radix Tree/Trie，PATRICIA tree，以及bitwise版本的crit-bit tree。当然很多名字的意义其实有交叉。

模板：

nt son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
void insert(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}

// 查询字符串出现的次数
int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

Trie树字符串统计

题目：

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
char str[N];
int son[N][26],cnt[N],idx;
void insert(char *s){
    int p=0;
    for(int i=0;s[i];i++){
        int u=s[i]-'a';
        if(!son[p][u]) son[p][u]=++idx;
        p=son[p][u];
    }
    cnt[p]++;
}

int find(char *s){
    int p=0;
    for(int i=0;s[i];i++){
        int u=s[i]-'a';
        if(!son[p][u]) return 0;
        p=son[p][u];
    }
    return cnt[p];
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        char op[2];
        scanf("%s%s",op,str);
        if(op[0]=='I') insert(str);
        else printf("%d\n",find(str));
    }
}

最大异或对

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=31*N;

int son[M][2],a[N],idx;

void insert(int x){
    int p=0;
    for(int i=30;i>=0;i--){
        int u=(x>>i)&1;
        if(!son[p][u]) son[p][u]=++idx;
        p=son[p][u];
    }
}

int find(int x){
    int p=0;
    int res=0;
    for(int i=30;i>=0;i--){
        int u=(x>>i)&1;
        if(son[p][!u]){//判断当前数对应位相对的那一位是否为1
            res=res*2+1;//res+=i<<i;将二进制转成int型的数。
            p=son[p][!u];
        }
        else{
            res=res*2+0;
            p=son[p][u];
        }
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        insert(a[i]);
    }
    int ans=-1;
    for(int i=0;i<n;i++){
        // cout<<find(a[i])<<" ";
        // cout<<endl;
       ans=max(ans,find(a[i])); 
    }
    cout<<ans<<endl;
    return 0;
}

小Q与彼岸花

题意：给你一个序列a1~an；m个询问，每一个询问包括一个l和r；问在l，r选择两个数异或最大是多少。

思路：跟上面那题差不多，但是m次询问，需要在询问外预处理答案，降低时间复杂度。

代码：

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
int ans[5010][5010];
int a[5010];
int son[5010*31][2],idx;
void insert(int x)
{
    int p = 0; //
    for (int i = 12; i >= 0; 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, ret = 0;
    for (int i = 12; i >= 0; i--)
    {
        int u = x >> i & 1;
        if (!son[p][!u])
        {
            p = son[p][u];
            ret = ret * 2 + u;
        }
        else
        {
            p = son[p][!u];
            ret = ret * 2 + !u;
        }
    }
    ret = ret ^ x;
    return ret;
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1 ; i<=n ; i++) cin>>a[i];
    for(int i=1 ; i<=n ; i++)//预处理答案
    {
        memset(son,0,sizeof son);
        idx=0;
        for(int j=i ; j<=n ; j++)
        {
            insert(a[j]);
            ans[i][j]=max(ans[i][j-1],query(a[j]));
        }
    }
    while(m--)
    {
        int l,r;
        cin>>l>>r;
        cout<<ans[l][r]<<endl;
    }
    return 0;
}