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:

**First time united by dsu**

**Asking range queries**

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>

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)

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`

.

The codes are nice.

But this line is very sad.

Oh, its just reference :)