#include <iostream>
using namespace std;
template <class TYPE> class segments_tree
{
TYPE *SegmentTree;
size_t base_capacity = 0;
TYPE (*g)(TYPE, TYPE);
TYPE neutral;
/*
TYPE:
Type of elements in the tree.
SegmentTree: (pointer)
Array-based tree of elements.
base_capacity: (unsigned integer value)
Parental array size, rounded to the closest upper power of 2.
g: (pointer)
Pointer to the funtion (associative binary operation), applied on the given array of elements.
WARNING: The given function must be associative. The monoidal structure of the tree will be ruined otherwise.
neutral: (array element)
The value of element, which is neutral relatively to "g" function.
################################
#### INNER HELPER FUNCTIONS ####
################################
result_on_segment_in:
returns value on segment [l, r];
*/
TYPE result_on_segment_in
(
size_t v, size_t tl,
size_t tr, size_t l,
size_t r
)
{
if (l > r) return neutral;
else if (l == tl && r == tr) return SegmentTree[v];
else
{
size_t tm = (tl + tr) / 2;
return g(result_on_segment_in(v*2, tl, tm, l, min(r,tm)),
result_on_segment_in(v*2+1, tm+1, tr, max(l,tm+1), r));
}
}
/*
make_monoid_and_fill_rest:
- fills the unused space of array (which appears due to rounding of size of parental array)
with neutral elements.
- assigns the necessary values to the upper "vertexes" of the tree.
*/
void make_monoid_and_fill_rest(TYPE *NewTree, const size_t &n, TYPE f(TYPE, TYPE), const TYPE &neutr)
{
g = f;
neutral = neutr;
for(size_t i = base_capacity+n; i < 2*base_capacity; ++i)
{
NewTree[i] = neutral;
}
for(size_t i = base_capacity-1; i > 0; --i)
{
NewTree[i] = g(NewTree[2*i], NewTree[2*i+1]);
}
SegmentTree = NewTree;
}
/*
fix_capacity:
Rounds base_capacity of the base array to closest upper power of 2.
*/
void fix_capacity(const size_t &base_array_size)
{
for (base_capacity = 1; base_capacity < base_array_size; base_capacity <<= 1);
}
public:
/*
##########################
#### PUBLIC FUNCTIONS ####
##########################
Definitions:
n - amount of elements in the parental array;
lb - binary logarithm.
Lowest level of the tree - parental array (segment of elements, which is a base of the tree)
and (if exists) unused space, filled with neutral elements.
construct:
Constructs the tree by copying elements of [begin; end) memory block into the segment tree,
and by building tree's structure using the given binary operation "f" and its neutral element "neutr".
Complexity: O(n).
*/
void construct(const TYPE *begin, const TYPE *end, TYPE f(TYPE, TYPE), const TYPE neutr)
{
size_t base_size = end - begin;
fix_capacity(base_size);
TYPE *NewTree = new TYPE[base_capacity*2];
for(size_t i = 0; i < base_size; ++i)
{
NewTree[base_capacity+i] = begin[i];
}
make_monoid_and_fill_rest(NewTree, base_size, f, neutr);
}
/*
read_and_construct:
Constructs the tree by filling with it with elements, created by "preprocessing_function",
and by building tree's structure using the given binary operation "f" and its neutral element "neutr".
This method is useful for creating tree by giving preprocessing_function an ability to read
the data from the incoming stream, if the separate memorisation of the base array is not needed.
Complexity: O(n).
*/
void read_and_construct(const size_t amount_of_elements, TYPE preprocessing_function(), TYPE f(TYPE, TYPE), const TYPE neutr)
{
fix_capacity(amount_of_elements);
TYPE *NewTree = new TYPE[base_capacity*2];
for(size_t i = 0; i < amount_of_elements; ++i)
{
NewTree[base_capacity+i] = preprocessing_function();
}
make_monoid_and_fill_rest(NewTree, amount_of_elements, f, neutr);
}
/*
assign:
Assigns new value to the element of base array with given index.
Complexity: O(lb(n))
*/
void assign(const size_t index, const TYPE new_value)
{
SegmentTree[base_capacity+index] = new_value;
for (size_t i = (base_capacity+index)/2; i > 0; i /= 2)
{
SegmentTree[i] = g(SegmentTree[2*i], SegmentTree[2*i+1]);
}
}
/*
result_on_segment:
Returns value of operation on the given segment of parental array.
Complexity: O(lb(n)).
*/
TYPE result_on_segment (size_t l, size_t r)
{
return result_on_segment_in(1, 0, base_capacity-1, l, r);
}
};
int sum(int a, int b)
{
return a+b;
}
int main()
{
unsigned int n;
cin >> n;
segments_tree <int> DO;
DO.read_and_construct(n, [] () {int x; cin >> x; return x;}, sum, 0);
for (unsigned int i = 0; i < n; ++i)
{
cout << "Sum on segment [0; " << i << "]: " << DO.result_on_segment(0, i) << "\n";
}
return 0;
}