Hello Codeforces Community!
This is my first ever blog on Codeforces and I’m super excited to be here!
Please read this before proceeding
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 Trie and Bit Trie.
The purpose of this blog
This blog is intended for those seeking the template, and it also includes additional valuable content. Please ensure to read the entire blog.
The Story Behind This Blog
Recently, I encountered a problem that could be solved using a Trie(specifically Bit 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 providing an implementation of the Trie data structure in C++ without using pointers.
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.
Trie
Template
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);}
};
Inspired by
My Bit_Trie template
Sample Submission
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);}
};
Inspired by
Note
You can modify the query function based on the specific calculation you intend to perform. I included this as it might be useful to someone.
Here are some additional templates I have created that you may find useful:
Macros used in below templates
#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
Debug
Template
#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;}
Source
Linear_Sieve
Template
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];
}
}
Source
Sample submission
Reading source
Binary_Exponentiation
Template
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;
}
Reading source
Combinations_Number_Theory
Template
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;
Inspired by
Sample Submission
Reading source
Dijkstra
Template
template <typename T>
vector<T> dijkstra(const vector<array<T,2>> g[], int n, int s){
assert(s >= 0 && s < n);
vector<T> dist(n, numeric_limits<T>::max());
priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> pq;
dist[s] = 0;
pq.emplace(dist[s], s);
while(!pq.empty()){
auto [x, y] = pq.top();
pq.pop();
if(dist[y] != x) continue;
for(auto &c : g[y]){
auto [v, w] = c;
if(dist[y] + w < dist[v]){
dist[v] = dist[y] + w;
pq.emplace(dist[v], v);
}
}
}
return dist;
// returns numeric_limits<T>::max() <^_^> if there's no path
}
Inspired by
Sample Submission
Reading source
Disjoint_Set_Union
Template
struct Dsu {
vector<int> rt, siz;
int n, cc;
Dsu(int _n) : n(_n), cc(_n){
rt.resize(n), iota(all(rt), 0);
siz.assign(n, 1);
}
inline int find(int x){
return (x == rt[x] ? x : rt[x] = find(rt[x]));
}
inline bool merge(int x, int y){
x = find(x), y = find(y);
if(x == y) return 0;
rt[y] = x;
siz[x] += siz[y];
cc -= 1;
return 1;
}
inline bool same(int x, int y){
return find(x) == find(y);
}
inline int size(int x){
return siz[find(x)];
}
};
Inspired by
orz jiangly His submission and orz tourist His github link both
Sample Submission
Reading source
Minimum_Spanning_Tree
Template
struct Dsu {
vector<int> rt, siz;
int n, cc;
Dsu(int _n) : n(_n), cc(_n){
rt.resize(n), iota(all(rt), 0);
siz.assign(n, 1);
}
inline int find(int x){
return (x == rt[x] ? x : rt[x] = find(rt[x]));
}
inline bool merge(int x, int y){
x = find(x), y = find(y);
if(x == y) return 0;
rt[y] = x;
siz[x] += siz[y];
cc -= 1;
return 1;
}
inline bool same(int x, int y){
return find(x) == find(y);
}
inline int size(int x){
return siz[find(x)];
}
};
template <typename T>
struct Mst {
const vector<array<T,3>> &edges;
vector<int> order;
vector<int> ans_list;
Dsu Z; T res = 0;
Mst(int _n, const vector<array<T,3>> &_edges) : Z(_n), edges(_edges){
order.resize(sz(edges));
iota(all(order), 0);
sort(all(order), [&](int x, int y){
return edges[x][2] < edges[y][2];
});
}
inline vector<int> find(){
for(auto &id : order){
auto &e = edges[id];
auto &u = e[0], &v = e[1], &w = e[2];
if(Z.merge(u, v)){
ans_list.pb(id);
res += w;
}
}
return ans_list;
// returns edge ids of "minimum spanning forest"
}
};
Inspired by
Sample Submission
Reading source
Z_Function
Template
vector<int> Z_f(string &s){
int n = sz(s);
vector<int> z(n); // z[0] = 0
for(int i=1, l=0, r=0; i<n; i++){
if(i < r) z[i] = min(r-i, z[i-l]);
while(i + z[i] < n && s[z[i]] == s[i+z[i]]) z[i]++;
if(i + z[i] > r) l = i, r = i + z[i];
}
return z;
}
Sample Submission
Reading source
"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!
