Hello Codeforces Community!
This is my first ever blog on Codeforces and I’m super excited to be here!
I want to let you know that this is not a tutorial blog. There are already plenty of well-written tutorials (including video tutorials) available out there. This blog is focused exclusively on the implementation, assuming that you are already well-versed in Tries and Bit Tries.
This blog is intended for those seeking the template, and it also includes additional valuable content. Please ensure to read the entire blog.
Recently, I encountered a problem that could be solved using a Trie. This sparked my interest in learning the data structure to tackle that specific problem.
However, I soon realized that nearly every tutorial out there implements a Trie using pointers. Out of curiosity, I wanted to explore how to implement it without using pointers. I searched extensively online but, surprisingly, found no clear guidance.
Eventually, I decided to implement it on my own — and that’s exactly what led to the creation of this blog.
This blog focuses on the implementation of the Trie data structure without using pointers, following modern C++ practices.
So, after spending time exploring and experimenting, here is the Trie template I came up with. It's designed to be clean, efficient, and adheres to modern C++ practices.
constexpr int Z = 1000001;
int _trie[Z][26];
int _pre_cnt[Z];
int _cnt[Z];
int _tot;
struct Trie {
Trie(){
_tot = 0;
new_node();
}
inline int new_node(){
int x = _tot++;
for(auto &c : _trie[x]) c = 0;
_pre_cnt[x] = 0;
return x;
}
inline void add(string &s, int f = 1, int ptr = 0){
for(auto &c : s){
int &p = _trie[ptr][c-'a'];
if(!p) p = new_node();
ptr = p;
_pre_cnt[ptr] += f;
}
_cnt[ptr] += f;
}
inline int count(string &s, int ptr = 0){
for(auto &c : s){
if(_pre_cnt[_trie[ptr][c-'a']]){
ptr = _trie[ptr][c-'a'];
continue;
}
return 0;
}
return _cnt[ptr];
}
inline int pref_count(string &s, int ptr = 0){
for(auto &c : s){
if(_pre_cnt[_trie[ptr][c-'a']]){
ptr = _trie[ptr][c-'a'];
continue;
}
return 0;
}
return _pre_cnt[ptr];
}
inline array<int, 2> lcp(string &s, int ptr = 0){
array<int, 2> res {};
for(auto &c : s){
int &p = _trie[ptr][c-'a'];
if(!p) break;
ptr = p;
res[0] += 1;
}
res[1] = _pre_cnt[ptr];
return res;
}
inline ll query(string &s, int ptr = 0, ll res = 0){
for(auto &c : s){
int &p = _trie[ptr][c-'a'];
if(!p) break;
ptr = p;
res += _pre_cnt[ptr];
}
return res; // lcp_sum
}
inline void remove(string &s, int f = -1) {add(s, f);}
};
My Bit_Trie template
constexpr int Z = 200000*31;
int _trie[Z][2];
int _cnt[Z];
int _tot;
struct Bit_Trie {
Bit_Trie(){
_tot = 0;
new_node();
}
inline int new_node(){
int x = _tot++;
_trie[x][0] = _trie[x][1] = 0;
_cnt[x] = 0;
return x;
}
inline void add(int x, int f = 1){
for(int i=30, ptr=0; ~i; --i){
int &p = _trie[ptr][x>>i&1];
if(!p) p = new_node();
ptr = p;
_cnt[ptr] += f;
}
}
inline int query(int x, int res = 0){
for(int i=30, ptr=0; ~i; --i){
int b = x>>i&1;
if(_cnt[_trie[ptr][b^1]]) b ^= 1, res |= 1<<i;
ptr = _trie[ptr][b];
}
return res;
}
inline void remove(int x, int f = -1) {add(x, f);}
};
Here are some additional templates I have created that you may find useful:
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define ull unsigned long long
#define ll long long
#define pb push_back
constexpr int M = 998244353; //1E9+7
#ifdef INSANE
#define dbg(x...) cerr << #x << " : ["; _print(x)
#else
#define dbg(x...)
#endif
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "T" : "F");}
template <typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template <typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
void __print(vector<bool> &v) {int f = 0; cerr << '{'; for (auto &&i : v) cerr << (f++ ? "," : "") << (i ? "T" : "F"); cerr << "}";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
template <size_t N> void __print(bitset<N> x) {cerr << x;}
"I may add more templates in the future, if feasible."
Thanks for stopping by, and feel free to drop a comment or suggestion. Happy coding!
