I like to build my cp library. I am not aiming to fill it by each algo I have met, so content looks poor. Instead I am focusing on frequently used features or implement convenient api for powerful methods.

Also I like to rate cp libraries of others and currently I noticed that my lib have enough implementations which I never seen before, so I want to share it with community.

Hope it will inspire you to improve or rewrite your library and eventually rethink about some algorithms (which happens to me couple times).

#5 Centroid decomposition

graphs/trees/centriod_decomposition.cpp

This one is the perfect example of what I am calling convenient api. I've seen a lot of centroid decomposition snippets and almost all of them is template code or unfinished data structure with piece of code where you need to add your solution. I have snippet that doesn't need changes at all and I need to just call it.

centriod_decomposition(tree, [&](auto &g, size_t centroid, size_t sizeof_subtree) {
	//g - is current subtree and I can freely traverse it from centroid by dfs
});

Once I've seen almost similar implementation but author passed to lambda original tree and vector of blocked vertices. I feel this uncomfortable to code: you still need to take in mind that vertex can be inaccessible.

It has little overhead from coping graph but I have never stubbed on this because overall running time is more crucial.

#4 Parallel binary search

misc/parallel_binary_search.cpp

Well, it is actually not general (can't solve this) but I am working on this. This one about "find first version of data where query is satisfied".

It rarely used but api is really sweet. Here I need to describe scope where I set predicate, implement evolution of data and just commit all changes — internally all queries will be executed in necessary moments.

auto res_bs = parallel_binary_search(qn, m, [&](auto vc) {
	//usually create init data
	vc.pred = [&](size_t qi) {
		//check query in data and return true/false
	};
	//do changes of data and call vc.commit() on each
});

Some examples:

auto res_bs = parallel_binary_search(qn, m, [&](auto vc) {
	dsu g(n);
	vc.pred = [&](size_t qi) {
		auto [x, y, z] = queries[qi];
		if(g[x] == g[y]) return g.size(x) < z;
		return g.size(x) + g.size(y) < z;
	};
	for(auto [i, j] : edges) {
		g.unite(i, j);
		vc.commit();
	}
});

auto res_bs = parallel_binary_search(qn, n, [&](auto vc) {
	aggregator<node> t(n);
	vc.pred = [&](int qi) {
		auto [ql, qr, w] = queries[qi];
		return t(ql, qr).seg < w;
	};
	for(auto [_, i] : pa) {
		t.set_value(i, 1);
		vc.commit();
	}
});

As bonus this implementation has very low time and memory overhead. It not uses map or vector of vectors: you can store all unfinished ranges sorted by left and very easy to split it to new groups in place.

#3 ilist<T>

structs/ilist.cpp

Implicit splay tree with iterators (stl style). It has api close to std::vector and not invalidating iterators like in std::set.

ilist<int> a;
a.push_back(0);
a[0] = 10; //O(logn) access
a.assign(begin(vec), end(vec));
for(int &x : a) ++x; //traverse from begin to end

while(std::size(a) < 10) { //calls a.size()
	a.insert(begin(a), 1); //O(logn) insertion
}

ilist<int> b = a; //makes copy
a.insert(begin(a), b.extract(begin(b) + 3, begin(b) + 6)); //O(logn) cut
a.insert(end(a), std::move(b)); //moving without coping

auto it = a.at(5); //iterator to 5th item
assert(begin(a) + 5 == it); //iterator advance in O(logn)
assert(it - begin(a) == 5); //iterators distance in O(logn)
assert(std::next(it) - begin(a) == 6); //also has ++it
assert(std::prev(it) - begin(a) == 4); //and --it

This snippet is biggest one but is not in final state. As TODO I want to implement reversible option and build link-cut trees that use it as black box.

#2 NTT (with modulos calculated in compile time)

numeric/ntt.cpp

My ntt is very default and maybe slow but it have no hardcoded ntt-frendly modulos. Actually I can understand why you add 3-5 modulos in ntt snippet but what I do not is hardcoding attendant stuff for it like roots. Seriously all this can be calculated in runtime easily. But with power of c++ all modulos can be calculated too!

As result convolution receives parameters and compiler will generate modulos that satisfy them.

convolution<modint<998244353>>(a, b); //will recognise as ntt-mod
convolution<modint<786433>>(a, b); //same! check codeforces.com/gym/100341/problem/C
convolution<modint<1000000007>>(a, b); //will generate 3 modulos and combine result by CRT
convolution<uint64_t, 1<<20 ,5>(a, b); //will generate 5 modulos good for length at most 2**20

#1 Hashing

And finally my favorite... strings/hasher.cpp

My hashing snippet uses famous rolling hash with $$$mod = 2^{61}-1$$$ with magic bit multiplication which works really fast.

Lets define core usual primitives about hashing and just implement it:

hash_t — wrapper of uint64_t containing raw hash (special case of modint)

hashed — what remains from string after it... hashed: hash_t and its length

hashed h = str; //from std::string
h.length() // length of hashed string
if(h1 == h2) // equality check in O(1)
h = h1 + h2; // concatenations in O(1)
h += 'a';

hasher — hash array of string/vector, allows get hash on range in O(1)

hash_span — reference to some range in hasher

hasher a(str), arev(rbegin(str), rend(str));
a.substr(start, length); // hashed
a.subhash(start, length); // hash_t
hash_span s = a(l, r); 
assert(s.length() == r - l);
assert(a[s.start()] == s[0]);

hash_span also have overloaded operator< (in $$$O(\log len)$$$) which can be used in std::sort or std::lower_bound.