数据结构-线段树Trie

闲来没事写了个带前缀的线段树模版。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>

using namespace std;

struct Trie
{
    int val;
    Trie *next[26];
};

void insert(Trie *root, string s)
{
    Trie *p = root;
    for (auto i = s.begin(); i != s.end(); i++) {
        int idx = *i - 'a';
        if (p->next[idx] == nullptr) {
            p->next[idx] = new Trie;
        }
        p = p->next[idx];
        p->val++;
    }
}

Trie *search(Trie *root, string s)
{
    Trie *p = root;
    for (auto i = s.begin(); i != s.end(); i++) {
        int idx = *i - 'a';
        if (p->next[idx] == nullptr) {
            return nullptr;
        }
        p = p->next[idx];
    }
    return p;
}

void remove(Trie *root, string s)
{
    Trie *p = root;
    int k = search(root, s)->val;
    if (k == 0) {
        return;
    }
    for (auto i = s.begin(); i != s.end(); i++) {
        int idx = *i - 'a';
        p = p->next[idx];
        p->val -= k;
    }
    for (int i = 0; i < 26; i++) {
        p->next[i] = nullptr;
    }
}

int main()
{
    Trie *root = new Trie;
    
    return 0;
}