Hey CodeForces,

**TL;DR** How to support different callable types as a template argument?

Data structures like segment tree, sparse table, fenwick tree, etc support various operations like max, min, gcd, sum etc. So it would be convenient to write a generic class for the data structure which takes the required operation as an input while constructing the object of the data structure, much in same spirit that `std::sort`

takes various comparators. The binary operation would then be the data member of the data structure's class.

The problem while implementing the operation as a template parameter is that there are many callable types like: lambdas, functors, functions (`std::min`

, `std::gcd`

), function objects(`std::less<int>`

, `std::plus<int>`

), `std::function`

.

One solution would be:

For functions like `std::min`

, `std::gcd`

to work co-exist std::plus, there will a requirement for a functor with `operator()`

implementing desired functionality. Then the functor can be used a template argument and it would be easy. But it certainly is not convenient to wrap the existing functions like `std::gcd`

, `std::max`

, `std::min`

to a class.

*Something* like this would be ideal:

```
sparse_table<int, std::plus<int>> st;
sparse_table<int, std::min<int>> st;
```

Is there a cleaner solution for this?

Wow, it just so happens that I wrote a generic sparse table struct yesterday after I encountered a problem on it.

It turned out to be not slower than my original code with normal sparse tables.

But I have to say, after writing it, it felt too complicated and I will most likely not use it again. Instead I'll have pre-written sparse tables ready; that will be easier. But I guess you're looking for the concept of passing functions so here is how I did it:

codeI needed a parent(on tree) sparse table for computing LCA. I also needed a minimum weight over path(on tree also) which uses the parent sparse table. Here is how I instantiated them:

codeAs I said, I would rather keep instances of the different possible types of sparse tables instead of this. By that I mean there are ones based on trees, and ones on arrays. You can see the resemblance between

`parent`

and`minW`

above since they are both based on trees. Look at these two simple sum and minimum on array sparse tables to see how they resemble as well:codeHave fun! :)

EDIT: here is the full submission if you want: https://ideone.com/fOwLE0It is possible to pass your binary operator through a template. Here is my implementation of a disjoint sparse table which accepts an arbitrary type and associative function:

codeSo, you have to define the function beforehand and then pass it to the template. A little more cumbersome than using a lambda inline passed to the constructor, but probably faster.

Thanks for the suggestion but you will still need to create a separate function for every operation you'll use whereas in this case, it would be simpler to use

`dst<int, std::plus<int>>`

if you'd used`class F`

instead of`T F(T,T)`

.Yes, however std::plus and std::min are fundamentally two different types of objects, so you couldn't make a simple template that works for both, as far as I know. My approach gives the user the most freedom over what to choose. e.g., if I want a matrix multiplication function, I can do that easily by just writing the function, rather than having to create my own class to match std::plus. In my experience, it's more convenient despite being more verbose.