Class: segment_tree

This is a basic segment tree template.

Don't know about segment tree?

Well, segment tree is a kind of data structure, which can solve some interval problems very fast.

For example, give you an array which is made up of integers. Can you do the following modifications in the level of log n?

Add a number to an element in the array. like: [1, 3, 2, 5, 6] -> [1, 3, 2, 5, 9]
Ask the sum in [l, r]. like: [1, 3, 2, 5, 9] (Ask [2, 4]) -> 10 (3+2+5=10)

Whether you can or can't, segment tree can! It even can do some harder modifications in the level of log n!

Now let us know how to make it work.

Definition

template<__id_type _Size, typename _Val_t, typename _Calc> class segment_tree

_Size: The size/length of the interval.
_Val_t: The data type of the interval.
_Calc: What should this class do. Just like sum in the last example. It's an operation.

In fact, you may not have to input _Calc. The default is sum. But if you want to use your own operation, your class have to include these things:

operator(): That's what the class do. You can put your operation in it.
operator^: It's just like pow. If you use a^b, The result is the same with calculating x = calc(x,a) to repeat b times.
identity(Variable, or calls 'e'): It's the identity element of this operation. It satisfies that a * e = a.

segment_tree<_Size, _Val_t, _Calc>::segment_tree() The default construction function. It builds an empty tree which fills identity in it.