fork download
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. template <class TYPE> class segments_tree
  5. {
  6. TYPE *SegmentTree;
  7. size_t base_capacity = 0;
  8. TYPE (*g)(TYPE, TYPE);
  9. TYPE neutral;
  10.  
  11. /*
  12. TYPE:
  13. Type of elements in the tree.
  14.  
  15. SegmentTree: (pointer)
  16. Array-based tree of elements.
  17.  
  18. base_capacity: (unsigned integer value)
  19. Parental array size, rounded to the closest upper power of 2.
  20.  
  21. g: (pointer)
  22. Pointer to the funtion (associative binary operation), applied on the given array of elements.
  23. WARNING: The given function must be associative. The monoidal structure of the tree will be ruined otherwise.
  24.  
  25. neutral: (array element)
  26. The value of element, which is neutral relatively to "g" function.
  27.  
  28. ################################
  29. #### INNER HELPER FUNCTIONS ####
  30. ################################
  31. result_on_segment_in:
  32. returns value on segment [l, r];
  33. */
  34. TYPE result_on_segment_in
  35. (
  36. size_t v, size_t tl,
  37. size_t tr, size_t l,
  38. size_t r
  39. )
  40. {
  41. if (l > r) return neutral;
  42. else if (l == tl && r == tr) return SegmentTree[v];
  43. else
  44. {
  45. size_t tm = (tl + tr) / 2;
  46. return g(result_on_segment_in(v*2, tl, tm, l, min(r,tm)),
  47. result_on_segment_in(v*2+1, tm+1, tr, max(l,tm+1), r));
  48. }
  49. }
  50.  
  51. /*
  52. make_monoid_and_fill_rest:
  53. - fills the unused space of array (which appears due to rounding of size of parental array)
  54. with neutral elements.
  55. - assigns the necessary values to the upper "vertexes" of the tree.
  56. */
  57. void make_monoid_and_fill_rest(TYPE *NewTree, const size_t &n, TYPE f(TYPE, TYPE), const TYPE &neutr)
  58. {
  59. g = f;
  60. neutral = neutr;
  61. for(size_t i = base_capacity+n; i < 2*base_capacity; ++i)
  62. {
  63. NewTree[i] = neutral;
  64. }
  65. for(size_t i = base_capacity-1; i > 0; --i)
  66. {
  67. NewTree[i] = g(NewTree[2*i], NewTree[2*i+1]);
  68. }
  69. SegmentTree = NewTree;
  70. }
  71.  
  72. /*
  73. fix_capacity:
  74. Rounds base_capacity of the base array to closest upper power of 2.
  75. */
  76. void fix_capacity(const size_t &base_array_size)
  77. {
  78. for (base_capacity = 1; base_capacity < base_array_size; base_capacity <<= 1);
  79. }
  80.  
  81. public:
  82. /*
  83. ##########################
  84. #### PUBLIC FUNCTIONS ####
  85. ##########################
  86. Definitions:
  87. n - amount of elements in the parental array;
  88. lb - binary logarithm.
  89. Lowest level of the tree - parental array (segment of elements, which is a base of the tree)
  90. and (if exists) unused space, filled with neutral elements.
  91.  
  92.  
  93. construct:
  94. Constructs the tree by copying elements of [begin; end) memory block into the segment tree,
  95. and by building tree's structure using the given binary operation "f" and its neutral element "neutr".
  96. Complexity: O(n).
  97. */
  98. void construct(const TYPE *begin, const TYPE *end, TYPE f(TYPE, TYPE), const TYPE neutr)
  99. {
  100. size_t base_size = end - begin;
  101. fix_capacity(base_size);
  102. TYPE *NewTree = new TYPE[base_capacity*2];
  103. for(size_t i = 0; i < base_size; ++i)
  104. {
  105. NewTree[base_capacity+i] = begin[i];
  106. }
  107. make_monoid_and_fill_rest(NewTree, base_size, f, neutr);
  108. }
  109.  
  110. /*
  111. read_and_construct:
  112. Constructs the tree by filling with it with elements, created by "preprocessing_function",
  113. and by building tree's structure using the given binary operation "f" and its neutral element "neutr".
  114. This method is useful for creating tree by giving preprocessing_function an ability to read
  115. the data from the incoming stream, if the separate memorisation of the base array is not needed.
  116. Complexity: O(n).
  117. */
  118. void read_and_construct(const size_t amount_of_elements, TYPE preprocessing_function(), TYPE f(TYPE, TYPE), const TYPE neutr)
  119. {
  120. fix_capacity(amount_of_elements);
  121. TYPE *NewTree = new TYPE[base_capacity*2];
  122. for(size_t i = 0; i < amount_of_elements; ++i)
  123. {
  124. NewTree[base_capacity+i] = preprocessing_function();
  125. }
  126. make_monoid_and_fill_rest(NewTree, amount_of_elements, f, neutr);
  127. }
  128.  
  129. /*
  130. assign:
  131. Assigns new value to the element of base array with given index.
  132. Complexity: O(lb(n))
  133. */
  134. void assign(const size_t index, const TYPE new_value)
  135. {
  136. SegmentTree[base_capacity+index] = new_value;
  137. for (size_t i = (base_capacity+index)/2; i > 0; i /= 2)
  138. {
  139. SegmentTree[i] = g(SegmentTree[2*i], SegmentTree[2*i+1]);
  140. }
  141. }
  142.  
  143. /*
  144. result_on_segment:
  145. Returns value of operation on the given segment of parental array.
  146. Complexity: O(lb(n)).
  147. */
  148. TYPE result_on_segment (size_t l, size_t r)
  149. {
  150. return result_on_segment_in(1, 0, base_capacity-1, l, r);
  151. }
  152. };
  153.  
  154. int sum(int a, int b)
  155. {
  156. return a+b;
  157. }
  158.  
  159. int main()
  160. {
  161. unsigned int n;
  162. cin >> n;
  163. segments_tree <int> DO;
  164. DO.read_and_construct(n, [] () {int x; cin >> x; return x;}, sum, 0);
  165. for (unsigned int i = 0; i < n; ++i)
  166. {
  167. cout << "Sum on segment [0; " << i << "]: " << DO.result_on_segment(0, i) << "\n";
  168. }
  169. return 0;
  170. }
Success #stdin #stdout 0s 16064KB
stdin
7
1 2 3 4 5 6 7
stdout
Sum on segment [0; 0]: 1
Sum on segment [0; 1]: 3
Sum on segment [0; 2]: 6
Sum on segment [0; 3]: 10
Sum on segment [0; 4]: 15
Sum on segment [0; 5]: 21
Sum on segment [0; 6]: 28