Trie

A tree in which each edge is labelled by a character, so that every root-to-node path spells a prefix. Insertion and lookup are $O(|w|)$ — independent of how many words are stored.

Implementation

Array-based, which is what you want in a contest:

struct Trie {
    static const int A = 26;
    vector<array<int, A>> nxt;
    vector<int> cnt, endCnt;                 // words through / ending at this node
 
    Trie() { newNode(); }
    int newNode() { nxt.push_back({}); nxt.back().fill(-1); cnt.push_back(0); endCnt.push_back(0); return nxt.size() - 1; }
 
    void insert(const string& s) {
        int v = 0;
        for (char ch : s) {
            int c = ch - 'a';
            if (nxt[v][c] == -1) nxt[v][c] = newNode();
            v = nxt[v][c];
            cnt[v]++;
        }
        endCnt[v]++;
    }
 
    bool contains(const string& s) {
        int v = 0;
        for (char ch : s) {
            int c = ch - 'a';
            if (nxt[v][c] == -1) return false;
            v = nxt[v][c];
        }
        return endCnt[v] > 0;
    }
 
    int countPrefix(const string& p) {        // how many stored words start with p
        int v = 0;
        for (char ch : p) {
            int c = ch - 'a';
            if (nxt[v][c] == -1) return 0;
            v = nxt[v][c];
        }
        return cnt[v];
    }
};

Memory: $O(\sum |w_i|\cdot \sigma )$ with array children. For $\sigma =26$ and $10^6$ total characters that is 104 MB of int — often too much. Use a map<char,int> per node ($O(\log \sigma )$ lookup, much less memory), or a compressed trie (see below).

What a trie answers

Query	Cost
Is $w$ present?	$O(|w|)$
How many words have prefix $p$?	$O(|p|)$ with a cnt field
Longest prefix of $w$ that is a stored word	$O(|w|)$
Lexicographically $k$-th word	$O(|w|\sigma )$, walking with subtree counts
All words with prefix $p$	$O(|p|+\text{output})$
Autocomplete	the same
Count distinct substrings	insert every suffix — $O(n^2)$; use a suffix automaton for $O(n)$

Compressed trie (radix tree / Patricia)

Merge every chain of single-child nodes into one edge labelled with a substring. The node count drops to $O(\text{number of words})$ regardless of word length, at the cost of more complex insertion (edges must sometimes be split).

A suffix tree is exactly the compressed trie of all suffixes.

The binary trie

Store integers as fixed-width bit strings (usually 30 or 32 bits) and insert them into a binary trie. That gives:

• Maximum XOR pair — greedily walk the opposite bit at each level;
• Maximum XOR of a query value with the set — same walk;
• Count values $<x$ / $k$-th smallest — subtree counts;
• XOR with a range constraint — walk with bounds.

This is one of the most reused structures in competitive programming; see Binary Trie.

Deletion

Decrement cnt along the path and endCnt at the end. Physically removing nodes is rarely worth it — the memory is already allocated, and a zero cnt behaves as absent.

Trie vs hash set

	Trie	Hash set
Lookup	$O(|w|)$	$O(|w|)$ (hashing)
Prefix queries	yes	no
Ordered iteration	yes (lexicographic)	no
Memory	high	low
Worst case	guaranteed	hash collisions

Use a trie when prefixes matter. For plain membership, a hash set is smaller and simpler.

Related structures

• Aho-Corasick — a trie plus suffix links, for multi-pattern matching
• Suffix automaton — a DAG rather than a tree; linear size for all substrings
• Eertree — a trie-like structure over palindromic substrings
• Persistent trie — versioned, for “XOR queries over a prefix of the array”

See also: Binary Trie · Aho-Corasick · Trie and Compressed Trie