# Trie (prefix tree)

## Example

Wordlist:

word
in
inn
algo
algae
stop


Tree: For all node, keep:

• Words ending at that node (if repeats aren't allowed, instead store a bool: is this a word or just a prefix node)
• No. of words that include this as a prefix

### Add a word

• $O(\text{length of word})$
• Traverse through the tree, and update the numbers accordingly
• Insert nodes when necessary

## Sample question

### Q1

Given array of integer $A$, and integers queries $Q$. For each query $q$ in $Q$, find the $i$ that gives maximum $q\text{ xor }A_i$.

$0 \leq A_i, Q_j < 2^3\ \forall\ i, j \in R_A, R_Q$

• Construct a prefix tree for all elements in $A$ by its binary digits
• Traverse through the tree to find the max possible $\text{xor}$ value

### Q2 (unsolved)

Given array of integer $A$ of length $n$, find $l$ and $r$ ($0 \leq l \leq r < n$ such that $A_l\text{ xor }A_{l+1}\text{ xor }A_{l+2}\text{ xor ... xor }A_r$ is maximum.

• Define $\text{axor}(a[l..r] = A_l\text{ xor }A_{l+1}\text{ xor }A_{l+2}\text{ xor ... xor }A_r$
• $\text{axor}(a[i..j]) = \text{axor}(a[0..j])\text{ xor axor}(a[0..i])$
• Construct empty Trie $T$ .