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 Trie and Bit Trie.
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(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.
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);}
};
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:
#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;
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
}
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)];
}
};
orz jiangly His submission and orz tourist His github link both
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"
}
};
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;
}
"I may add more templates in the future, if feasible."
Experience with My First Blog on Codeforces
Writing my first blog on Codeforces was an hard exciting challenge. It took considerable time and effort to refine my ideas and present them clearly. The process helped me improve my technical writing and deepen my understanding of the topics I’ve discussed so far. The experience was incredibly rewarding and motivated me to continue sharing my knowledge. I’m looking forward to engaging more with the community and learning from any future responses.
Thanks for stopping by, and feel free to drop a comment or suggestion. Happy coding!
To be honest, I have never coded Trie with pointers.
And that must be the reason I can't get my rating better! I have no template to use and every time I'm typing a new oneTry to use
templateto allow more type of chars.Here is a sample of trie template that allow all type of chars.
Allow
std::maporstd::unordered_mapfor sons' index-based pointer container.Allow array for sons' index-based pointer container.
Instead of utilizing the template, we can simply increase the size from 26 to 128 to accommodate all characters in the Trie.
But what if we need to put
vector<int>instead ofstringinto a trie. Soon you will know how usefultemplateis.This is really helpful !!