fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. template <class TYPE, class MODIFICATION_TYPE> class segments_tree
  5. {
  6. 	TYPE *SegmentTree;
  7. 	MODIFICATION_TYPE* ModifierList;
  8. 	size_t base_capacity;
  9. 	TYPE (*g)(const TYPE&, const TYPE&);
  10. 	TYPE (*m)(const TYPE&, const size_t&, const size_t&, const MODIFICATION_TYPE&);
  11. 	MODIFICATION_TYPE (*combine_modifications)(const MODIFICATION_TYPE&, const MODIFICATION_TYPE&);
  12. 	TYPE neutral;
  13. 	MODIFICATION_TYPE neutral_modifier;
  14.  
  15. 	/*
  16. 	TYPE:
  17. 		Type of elements in the tree.
  18.  
  19. 	MODIFICATION_TYPE:
  20. 		Special type, which allows to synchronize modifications on segment.
  21.  
  22. 	SegmentTree: (pointer)
  23. 		Array-based tree of elements.
  24.  
  25. 	base_capacity: (unsigned integer value)
  26. 		Parental array size, rounded to the closest upper power of 2.
  27.  
  28. 	g: (pointer)
  29. 		Pointer to the funtion (associative binary operation), applied on the given array of elements.
  30. 		WARNING: The given function must be associative. The monoidal structure of the tree will be ruined otherwise.
  31.  
  32. 	m: (pointer)
  33. 		Pointer to the function, used to modify segments of the tree.
  34.  
  35. 	combine_modifications: (pointer)
  36. 		Pointer to the function, which combines old and new modifications to synchronize them.
  37.  
  38. 	neutral: (array element)
  39. 		The value of element, which is neutral relatively to "g" function.
  40.  
  41. 	neutral_modifier:
  42. 		Marker of non-modified vertexes.
  43.  
  44. 	################################
  45. 	#### INNER HELPER FUNCTIONS ####
  46. 	################################
  47. 	try_push: pushes the modifier value from vertex to its left and right leaf.
  48. 	*/
  49. 	void try_push(size_t& v, size_t& tl, size_t& tr)
  50. 	{
  51. 		if (v < base_capacity) if (ModifierList[v] != neutral_modifier)
  52. 		{
  53. 			size_t mid = (tr+tl)/2, i = 2*v;
  54. 			SegmentTree[i] = m(SegmentTree[i], tl, mid, ModifierList[v]);
  55. 			SegmentTree[i+1] = m(SegmentTree[i+1], ++mid, tr, ModifierList[v]);
  56.  
  57. 			if (i+1 < base_capacity)
  58. 			{
  59. 				ModifierList[i] = combine_modifications(ModifierList[i], ModifierList[v]);
  60. 				ModifierList[i+1] = combine_modifications(ModifierList[i+1], ModifierList[v]);
  61. 			}
  62.  
  63. 			ModifierList[v] = neutral_modifier;
  64. 		}
  65. 	}
  66.  
  67. 	/*
  68. 	assign_in:
  69. 		assigns a new values to the vertexes of the tree,
  70. 		which are responsible for the value of [l; r] segment.
  71. 	*/
  72. 	void assign_in
  73. 	(
  74. 		size_t v,
  75. 		size_t tl, size_t tr,
  76. 		size_t l, size_t r,
  77. 		const MODIFICATION_TYPE& new_modification
  78. 	)
  79. 	{
  80. 		if (l <= r)
  81. 		{
  82. 			try_push(v, tl, tr);
  83. 			if (l == tl && tr == r)
  84. 			{
  85. 				SegmentTree[v] = m(SegmentTree[v], tl, tr, new_modification);
  86. 				if (v < base_capacity) ModifierList[v] = new_modification;
  87. 			}
  88. 			else
  89. 			{
  90. 				size_t tm = (tl + tr) / 2;
  91.  
  92. 				assign_in(2*v, tl, tm, l, min(r,tm), new_modification);
  93. 				assign_in(2*v+1, tm+1, tr, max(l,tm+1), r, new_modification);
  94.  
  95. 				SegmentTree[v] = g(SegmentTree[2*v], SegmentTree[2*v+1]);
  96. 			}
  97. 		}
  98. 	}
  99.  
  100. 	/*
  101. 	result_on_segment_in:
  102. 		returns value on segment [l, r];
  103. 	*/
  104. 	TYPE result_on_segment_in
  105. 	(
  106. 		size_t v, size_t tl,
  107. 		size_t tr, size_t l,
  108. 		size_t r
  109. 	)
  110. 	{
  111. 		if (l > r) return neutral;
  112. 		else
  113. 		{
  114. 			if (l == tl && r == tr) return SegmentTree[v];
  115. 			else
  116. 			{
  117. 				try_push(v, tl, tr);
  118. 				size_t tm = (tl + tr) / 2;
  119. 				return g(result_on_segment_in(v*2, tl, tm, l, min(r,tm)),
  120. 				result_on_segment_in(v*2+1, tm+1, tr, max(l,tm+1), r));
  121. 			}
  122. 		}
  123. 	}
  124.  
  125. 	/*
  126. 	make_monoid_and_fill_rest:
  127. 		- fills the unused space of array (which appears due to rounding of size of parental array)
  128. 		with neutral elements.
  129. 		- assigns the necessary values to the upper "vertexes" of the tree.
  130. 	*/
  131. 	void make_monoid_and_fill_rest
  132. 	(
  133. 		TYPE *NewTree,
  134. 		const size_t &n,
  135. 		TYPE f(const TYPE&, const TYPE&),
  136. 		const TYPE &neutr,
  137. 		TYPE modifier_function(const TYPE&, const size_t&, const size_t&, const MODIFICATION_TYPE&),
  138. 		MODIFICATION_TYPE modification_combinator(const MODIFICATION_TYPE&, const MODIFICATION_TYPE&),
  139. 		const MODIFICATION_TYPE &new_neutral_modifier
  140. 	)
  141. 	{
  142. 		g = f;
  143. 		m = modifier_function;
  144. 		combine_modifications = modification_combinator;
  145. 		neutral = neutr;
  146. 		neutral_modifier = new_neutral_modifier;
  147. 		for(size_t i = base_capacity+n; i < 2*base_capacity; ++i)
  148. 		{
  149. 			NewTree[i] = neutral;
  150. 		}
  151. 		for(size_t i = base_capacity-1; i > 0; --i)
  152. 		{
  153. 			NewTree[i] = g(NewTree[2*i], NewTree[2*i+1]);
  154. 			ModifierList[i] = neutral_modifier;
  155. 		}
  156. 		ModifierList[0] = neutral_modifier;
  157. 		SegmentTree = NewTree;
  158. 	}
  159.  
  160. 	/*
  161. 	fix_capacity:
  162. 		Rounds base_capacity of the base array to closest upper power of 2.
  163. 	*/
  164. 	void fix_capacity(const size_t &base_array_size)
  165. 	{
  166. 		for (base_capacity = 1; base_capacity < base_array_size; base_capacity <<= 1);
  167. 	}
  168.  
  169. 	public:
  170. 	/*
  171. 	##########################
  172. 	#### PUBLIC FUNCTIONS ####
  173. 	##########################
  174. 	Definitions:
  175. 		n - amount of elements in the parental array;
  176. 		lb - binary logarithm.
  177. 		Lowest level of the tree - parental array (segment of elements, which is a base of the tree)
  178. 		and (if exists) unused space, filled with neutral elements.
  179.  
  180. 	construct:
  181. 		Constructs the tree by copying elements of [begin; end) memory block into the segment tree,
  182. 		and by building tree's structure using the given binary operation "f" and its neutral element "neutr".
  183. 		Complexity: O(n).
  184. 	*/
  185. 	void construct
  186. 	(
  187. 		const TYPE *begin,
  188. 		const TYPE *end,
  189. 		TYPE f(const TYPE&, const TYPE&),
  190. 		const TYPE neutr,
  191. 		TYPE modifier_function(const TYPE&, const size_t&, const size_t&, const MODIFICATION_TYPE&),
  192. 		MODIFICATION_TYPE modification_combinator(const MODIFICATION_TYPE&, const MODIFICATION_TYPE&),
  193. 		const MODIFICATION_TYPE new_neutral_modifier
  194. 	)
  195. 	{
  196. 		size_t base_size = end - begin;
  197. 		fix_capacity(base_size);
  198. 		TYPE *NewTree = new TYPE[base_capacity*2];
  199. 		ModifierList = new MODIFICATION_TYPE[base_capacity];
  200. 		for(size_t i = 0; i < base_size; ++i)
  201. 		{
  202. 			NewTree[base_capacity+i] = begin[i];
  203. 		}
  204. 		make_monoid_and_fill_rest(NewTree, base_size, f, neutr, modifier_function, modification_combinator, new_neutral_modifier);
  205. 	}
  206.  
  207. 	/*
  208. 	read_and_construct:
  209. 		Constructs the tree by filling with it with elements, created by "preprocessing_function",
  210. 		and by building tree's structure using the given binary operation "f" and its neutral element "neutr".
  211. 		This method is useful for creating tree by giving preprocessing_function an ability to read
  212. 		the data from the incoming stream, if the separate memorisation of the base array is not needed.
  213. 		Complexity: O(n).
  214. 	*/
  215. 	void read_and_construct
  216. 	(
  217. 		const size_t amount_of_elements,
  218. 		TYPE preprocessing_function(),
  219. 		TYPE f(const TYPE&, const TYPE&),
  220. 		const TYPE neutr,
  221. 		TYPE modifier_function(const TYPE&, const size_t&, const size_t&, const MODIFICATION_TYPE&),
  222. 		MODIFICATION_TYPE modification_combinator(const MODIFICATION_TYPE&, const MODIFICATION_TYPE&),
  223. 		const MODIFICATION_TYPE new_neutral_modifier
  224. 	)
  225. 	{
  226. 		fix_capacity(amount_of_elements);
  227. 		TYPE *NewTree = new TYPE[base_capacity*2];
  228. 		ModifierList = new MODIFICATION_TYPE[base_capacity];
  229. 		for(size_t i = 0; i < amount_of_elements; ++i)
  230. 		{
  231. 			NewTree[base_capacity+i] = preprocessing_function();
  232. 		}
  233. 		make_monoid_and_fill_rest(NewTree, amount_of_elements, f, neutr, modifier_function, modification_combinator, new_neutral_modifier);
  234. 	}
  235.  
  236. 	/*
  237. 	assign:
  238. 		Assigns new value to the element of base array with given index [i]
  239. 		or modifies the given segment [l, r], relatively to the modifier value.
  240. 		Complexity: O(lb(n))
  241. 	*/
  242. 	void assign(size_t i, const MODIFICATION_TYPE modifier)
  243. 	{
  244. 		assign_in(1, 0, base_capacity-1, i, i, modifier);
  245. 	}
  246.  
  247. 	void assign(size_t l, size_t r, const MODIFICATION_TYPE modifier)
  248. 	{
  249. 		assign_in(1, 0, base_capacity-1, l, r, modifier);
  250. 	}
  251.  
  252. 	/*
  253. 	result_on_segment:
  254. 		Returns value of operation on the given segment of parental array.
  255. 		Complexity: O(lb(n)).
  256. 	*/
  257. 	TYPE result_on_segment(size_t l, size_t r)
  258. 	{
  259. 		return result_on_segment_in(1, 0, base_capacity-1, l, r);
  260. 	}
  261. };
  262.  
  263. int main()
  264. {
  265. 	return 0;
  266. }
Success #stdin #stdout 0s 15224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/IjDkJz
UNIVERSAL SEGMENTS TREE (multi-modification)
language:
C++14 (gcc 8.3)
created:
7 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!