fork download
copy 
  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 15248KB
comments (?)
stdin
copy 
5
1 2 3 4 5
stdout
copy 
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
https://ideone.com/w1NFm7
UNIVERSAL SEGMENTS TREE (original)
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!