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?

1. Add a number to an element in the array. like: [1, 3, 2, 5, 6] -> [1, 3, 2, 5, 9]
2. 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 let it work.

Define

template<__id_type _Size, typename _Val_t> class segment_tree