Trie树

Tire树

我们一般实现字典树的两个功能, 插入操作和查询操作.

AcWing 835. Trie字符串统计

字典树模板题

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 200100;

int idx, a[N][30], st[N];

// 插入操作
void insert(string s)
{
    int n = s.size();
    int j = 0;
    for(int i = 0; i < n; i++)
    {
        int u = s[i] - 'a';
        if(a[j][u] == -1) 
            a[j][u] = ++idx;
            
        j = a[j][u];
    }
  	// 在叶子结点添加当前字符串的个数
    st[j]++;
}

// 查询操作
int query(string s)
{
    int n = s.size();
    int j = 0;
    for(int i = 0; i < n; i++)
    {
        int u = s[i] - 'a';
        if(a[j][u] == -1) return 0;
        j = a[j][u];
    }
    return st[j];
}

int main()
{
    memset(a, -1, sizeof a);
    idx = 1;
    int n;
    cin >> n;
    while(n--)
    {
        char OP;
        string s;
        cin >> OP >> s;
        if(OP == 'I') insert(s);
        if(OP == 'Q') cout << query(s) << endl;
    }
    
    return 0;
}

二刷代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100010;
int q[N][26];
int idx;
int st[N];

void insert(string s)
{
    int p = 0;
    for(auto &w:s)
    {
        int s = w - 'a';
        if(q[p][s]) 
        {
            p = q[p][s];
        }
        else
        {
            q[p][s] = ++idx;
            p = q[p][s];
        }
    }
    st[p]++;
}

int query(string s)
{
    int p = 0;
    for(auto &w:s)
    {
        int s = w - 'a';
        if(q[p][s]) p = q[p][s];
        else return 0;
    }
    return st[p];
}

int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        char OP;
        string s;
        cin >> OP >> s;
        if(OP == 'I') insert(s);
        else cout << query(s) << endl;
    }
    return 0;
}

AcWing 143. 最大异或对

字典树应用

我们要查询异或对, 只要不断向下搜索与当前位不同的数字即可

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 3100010;

int q[N][2];
int idx;
int a[N];

void insert(int x)
{
    int p = 0;
    for(int i = 30; ~i ; i--)
    {
      	// s为儿子
        auto &s = q[p][x >> i & 1];
      
      	// s不存在则创建一个s
        if(!s) s = ++idx;
        p = s;
    }
}

int query(int x)
{
    int ret = 0;
    int p = 0;
    for(int i = 30; ~i ; i--)
    {
        auto s = x >> i & 1;
        
        // 寻找相反的儿子
        if(q[p][!s])
        {
            ret += 1 << i;
            p = q[p][!s];
        }
        else p = q[p][s];
    }
    
    return ret;
}

int main()
{
    int n;
    cin >> n;
    for(int i = 0 ; i < n; i++)
    {
        cin >> a[i];
        insert(a[i]);
    }
    
    int ret = 0;
    for(int i = 0 ; i < n; i++)
    {
        ret = max(ret, query(a[i]));
    }
    
    cout << ret;
    return 0;
}

AcWing 3485. 最大异或和

思路:

我们用一个固定长度滑动窗口来维护一个固定的连续数组

定义两个操作字典树的函数, 插入和删除一个数字;

统计每一个二进制位的个数, 如果是奇数个, 那么异或之后得到的答案一定是1, 否则是0;

#include<iostream>
#include<cstring>
using namespace std;

const int N = 100010;
int a[N];
int st[N];

// 插入一个数
void insert(int x)
{
    for(int i = 30; ~i; i--)
        st[i] += x >> i & 1;
}

// 删除一个数
void deleted(int x)
{
    for(int i = 30; ~i; i--)
        st[i] -= x >> i & 1;
}

// 计算每一位的个数, 奇数是1, 偶数是0
int query()
{
    int ret = 0;
    for(int i = 30; ~i; i--)
        if(st[i] & 1) ret += 1 << i;
    return ret;
}

int main()
{
    int n,m;
    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    
  	// 维护一个固定滑动窗口
    int l = 0 , r = 0;
    for(int i = 0;i < m; i++) insert(a[r++]);
    
    int ret = 0;
    while(r <= n)
    {
        ret = max(ret, query());
        insert(a[r++]);
        deleted(a[l++]);
    }
    
    cout << ret;
    return 0;
}