Hello Codeforces,

It is sometimes required in competitive programming problems to segment a range defined as **[first, last)** of indices in a given data container, where **first** refers to the first element to inspect and **last** refers to the element past the last element to inspect, into a number of intervals such that all the consecutive elements in any interval have the same value of a particular segmentation function $$$f(x)$$$ whose value depends on the present element $$$x$$$ only, and this value is different from the function value in the intervals before and after such interval if any of them exists.

This blog presents a simple C++ template data structure for such purpose.

The following is the declaration and implementation of the data structure.

**struct seg**

The `seg`

data structure inherits `vector<size_t>`

as a base class to store the range-segmentation results. The data-structure constructor `seg(ForwardIt first, ForwardIt last, const UnaryFunction& fun)`

has three parameters: `first`

and `last`

specify the range **[first, last)**, and `fun`

specifies the segmentation function.

The time-complexity of constructing an object/instance of this data structure should be $$$O((S+T+U).N)$$$, where $$$S$$$, $$$T$$$ and $$$U$$$ are the execution times required to complete the segmentation function call `fun(*first)`

, to append an element to the vector using a `vector<size_t>::push_back(width)`

member function call, to increment the iterator `first`

, respectively, and $$$N = last-first$$$ is the range size.

The following are sample applications of this data structure.