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;}
vector<int> primes, lp, pf;
void Sieve(int n){
lp.assign(n+1, 0);
pf.assign(n+1, 0);
primes.clear();
for(int i=2; i<=n; i++){
if(!lp[i]){
primes.pb(i);
lp[i] = i;
pf[i] = 1;
}
for(auto &p : primes){
if(i*p > n) break;
lp[i*p] = p;
if(p == lp[i]){
pf[i*p] = pf[i];
break;
}
pf[i*p] = pf[i] + 1;
}
// pf[i] += pf[i-1];
}
}
template <typename T>
constexpr T power(ll a, T b, ull res = 1){
a %= M;
while(b){
if(b&1) (res *= a) %= M;
(a *= a) %= M;
b >>= 1;
}
return res;
}
template <typename T>
constexpr T power(ll a, T b, ull res = 1){
a %= M;
while(b){
if(b&1) (res *= a) %= M;
(a *= a) %= M;
b >>= 1;
}
return res;
}
template <typename T>
constexpr T inverse(T x) {return power(x, M-2);}
struct Comb {
int n;
vector<int> _fact, _invfact, _inv;
Comb() : n{0}, _fact{1}, _invfact{1}, _inv{0} {}
Comb(int _n) : Comb() {init(_n);}
void init(int m){
_fact.resize(m+1);
_invfact.resize(m+1);
_inv.resize(m+1);
for(int i=n+1; i<=m; i++){
_fact[i] = 1LL*_fact[i-1]*i%M;
}
_invfact[m] = inverse(_fact[m]);
for(int i=m; i>n; i--){
_invfact[i-1] = 1LL*_invfact[i]*i%M;
_inv[i] = 1LL*_invfact[i]*_fact[i-1]%M;
}
n = m;
}
int fact(int m){
if(m > n) init(2*m);
return _fact[m];
}
int invfact(int m){
if(m > n) init(2*m);
return _invfact[m];
}
int inv(int m){
if(m > n) init(2*m);
return _inv[m];
}
int binom(int n, int r){
if(n < r || r < 0) return 0;
return 1LL*fact(n)*invfact(r)%M*1LL*invfact(n-r)%M;
}
} comb;
"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!
