Trie -

Tries, or Prefix Trees, are data structures used to store strings. In a Binary Search Tree, each node will store the entire key, whereas in a trie, each node’s position in the tree will determine the key that it represents.

Tries are essentially rooted trees where each node (except for the root), will store some character. Every path from the root to any other node in the tree will represent a prefix of at least 1 other string.

A trie supports 2 main operations

Insert a string
Search for a string

Of course it is also possible to augment the information stored in the nodes in order to perform more complicated queries.

struct Node{
bool end; //is this node the ending of a word?
unordered_map<char, Node*> ch; //store my children
Node(){
end = false;
}
};

struct Trie{
Node *root;
Trie(){
root = new Node();
}
void insert(string c){
Node *current = root;
for(char nxt : c){
if(current->ch.find(nxt) == current->ch.end()){
current->ch[nxt] = new Node(); //create a new node
}
current = current->ch[nxt]; //traverse to this character
}
current->end = true; //we have reached the end of a word
}
bool find(string c){
Node *current = root;
for(char nxt : c){
if(current->ch.find(nxt) == current->ch.end()){
return false;
}
current = current->ch[nxt];
}
return current->end;
}
};

Notice how each path from the root to any node will be a prefix of any word since we traverse the tree from the root down as we insert nodes.

Problem: https://dmoj.ca/problem/xorm

This problem reduces to the following:

Given an array A, we have Q queries of the form x. Find the index i such that A[i] XOR x is minimized.

To solve this problem we can convert each of the numbers in the array to their binary representation and then insert them into a binary trie. To perform queries we simultaneously traverse the bits of the current query and the trie. At each bit, if it’s 1, then obviously we want the current trienode value to be 1 also (since 1 XOR 1 = 0). If 1 exists then we move towards that trie node, otherwise we move towards 0. The same process is done in reverse if the current bit is 0.

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define vt vector
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define ub upper_bound
#define lb lower_bound

template<typename T> inline void setmax(T& a,T b){a = (a > b ? a : b);}
template<typename T> inline void setmin(T& a,T b){a = (a < b ? a : b);}

const int inf = 0x3f3f3f3f, mod = (int)1e9 + 7, mx = (int)2e5 + 10;
const ll infll = 0x3f3f3f3f3f3f3f3f;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

struct node{
int val;
node *ch[2];
node(int v){
val = v;
}
};
struct trie_{
node *root = new node(inf);
trie_(int v){
root->val = inf;
}
void insert(int ind, int val){
node *chr = root;
for(int i=30; i >=0; i–){
if(val & (1 << i)){
if(chr->ch[1] == nullptr)chr->ch[1] = new node(inf);
chr = chr->ch[1];
}else{
if(chr->ch[0] == nullptr)chr->ch[0] = new node(inf);
chr = chr->ch[0];
} //simply inserting the binary representation into the trie
}
chr->val = min(chr->val, ind); //minimum index that has the current value
}
int qry(int x){
node *chr = root;
for(int i=30; i >= 0; i–){
if((x & (1 << i)) && chr->ch[1] != nullptr){ //found same bit, by XOR will set that bit to 0 so continue
chr = chr->ch[1];
}
else if(chr->ch[0] != nullptr)chr = chr->ch[0];
else if(chr->ch[1] != nullptr)chr = chr->ch[1];
else assert(false);
}
return chr->val;
}
};

int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
trie_ t(inf);
int n, q; cin >> n >> q;
for(int i=0; i < n; i++){
int x; cin >> x;
t.insert(i, x);
}
int to = 0;
while(q–){
int v; cin >> v;
to ^= v;
cout << t.qry(to) << ‘\n’;
}
}

Extensions:

Persistent Tries

Nested Tries