fork download
copy 
  1. /** By Avikalp Srivastava **/
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include<string.h>
  6. #include<math.h>
  7.  
  8. // Get the mid value of the interval [s,e]
  9. int get_mid(int s, int e)
  10. {
  11. 	return s+(e-s)/2;
  12. }
  13.  
  14. // Will be used for constructing the segment tree by the constructing function construct_st
  15. int construct_st_util(int A[],int ss,int se,int st[],int si);
  16.  
  17. // A[] : Array for which segment tree is constructed
  18. // n : size of array A[]
  19. int* construct_st(int A[],int n)
  20. {
  21. 	int x= (int)(ceil)(log2(n));
  22. 	int size= 2*(int)pow(2,x)-1;
  23. 	// Allocating proper amount of memory to st(segment tree)
  24. 	int* st = (int *)malloc(size*sizeof(int));
  25. 	// Calling helper function
  26. 	construct_st_util(A,0,n-1,st,0);
  27. 	return st;
  28. }
  29.  
  30. // ss : start of segment
  31. // se : segment end
  32. // st[] : segment tree of array A[]
  33. // si : current index during traversal in the segment tree
  34. // Parameters passed initially : A[] -> original array, ss -> 0, se -> n-1, st[] -> array with apt allocated mem, si -> 0
  35. int construct_st_util(int A[],int ss,int se,int st[],int si)
  36. {
  37.     // If interval length is zero, we pass the array value to st[si]
  38. 	if(ss==se)
  39. 	{
  40. 		st[si]=A[ss];
  41. 		return st[si];
  42. 	}
  43.  
  44. 	// Recursive calls to the left and right children and adding them to get value for current node
  45. 	int mid= get_mid(ss,se);
  46. 	st[si]=(construct_st_util(A,ss,mid,st,2*si+1)+construct_st_util(A,mid+1,se,st,2*si+2));
  47. 	return st[si];
  48. }
  49.  
  50. // Helper to get_sum function
  51. // Lazy array may have some updates to be made
  52. // ss : segment start of current probe
  53. // se : segment end of current probe
  54. // qs : query start provided by user
  55. // qe : query end provided by the user
  56. // si : current segment tree index in probe
  57. int get_sum_util(int st[],int lazy[],int ss,int se,int qs, int qe,int si)
  58. {
  59. 	// If there are pending updates, complete them and assign lazy values to children
  60. 	if(lazy[si]!=0)
  61. 	{
  62. 		st[si]=lazy[si]*(se-ss+1);
  63. 		// If the node is not a leaf
  64. 		if(ss!=se)
  65. 		{
  66. 			lazy[2*si+1]=lazy[si];
  67. 			lazy[2*si+2]=lazy[si];
  68. 		}
  69. 		// This node now has no pending updates
  70. 		lazy[si]=0;
  71. 	}
  72.  
  73. 	if(ss>=qs&&se<=qe) return st[si];                   // completely within query range, return updated sum value
  74. 	if(ss>se||ss>qe||se<qs) return 0;                   // completely out of query range, nothing to do
  75.  
  76. 	// Partial Overlap case
  77. 	int mid = get_mid(ss,se);
  78. 	return (get_sum_util(st,lazy,ss,mid,qs,qe,2*si+1)+get_sum_util(st,lazy,mid+1,se,qs,qe,2*si+2));
  79. }
  80.  
  81. // Get_sum of array elements from qs to qe
  82. int get_sum(int st[],int lazy[],int n,int qs,int qe)
  83. {
  84. 	return get_sum_util(st,lazy,0,n-1,qs,qe,0);
  85. }
  86.  
  87. // Helper to update_val function
  88. // ss : segment start of current probe
  89. // se : segment end of current probe
  90. // qs : query start provided by user
  91. // qe : query end provided by the user
  92. // si : current segment tree index in probe
  93. // Updates array elements from qs to qe to new_val by postponing updates and assigning them to lazy values
  94. void update_val_util(int st[],int lazy[],int ss,int se,int qs,int qe,int new_val,int si)
  95. {
  96. 	// If there are pending updates to the current node, complete them.
  97. 	if(lazy[si]!=0)
  98. 	{
  99. 		st[si]=lazy[si]*(se-ss+1);
  100. 		// If node is not a leaf
  101. 		if(se!=ss)
  102. 		{
  103. 			lazy[si*2+1]=lazy[si];
  104. 			lazy[2*si+2]=lazy[si];
  105. 		}
  106. 		// No pending updates to the current node
  107. 		lazy[si]=0;
  108. 	}
  109.  
  110. 	if(ss>se||qs>se||qe<ss) return; 	// current node is out of query range, nothing to do.
  111.  
  112. 	if(ss>=qs&&qe>=se)					// current node is completely in query range, update it and assign lazy values to children
  113. 	{
  114. 		st[si]=(new_val)*(se-ss+1);
  115. 		// If current node is not a leaf
  116. 		if(ss!=se)
  117. 		{
  118. 			lazy[2*si+1]=new_val;
  119. 			lazy[2*si+2]=new_val;
  120. 		}
  121. 		return;						  // Since current node was completely in range and lazy values have been assigned to children, no need to recurse further
  122. 	}
  123.  
  124. 	// In case the current node's range partially overlaps with the query range
  125. 	int mid = get_mid(ss,se);
  126. 	update_val_util(st,lazy,ss,mid,qs,qe,new_val,2*si+1);		// Update left child
  127. 	update_val_util(st,lazy,mid+1,se,qs,qe,new_val,2*si+2);		// Update right child
  128.  
  129. 	st[si]=st[2*si+1]+st[2*si+2];								// Current node is sum of children
  130. }
  131.  
  132. // Called for updating array elements from qs to qe to new_val.
  133. void update_val(int A[],int lazy[],int n,int qs,int qe,int new_val,int st[])
  134. {
  135. 	update_val_util(st,lazy,0,n-1,qs,qe,new_val,0);
  136. }
  137.  
  138. // Used for constructing lazy array with apt memory and initialisation.
  139. int* construct_lazy(int n)
  140. {
  141. 	int *lazy,i;
  142. 	int x= (int)((ceil)(log2(n)));
  143. 	int size= 2*(int)pow(2,x)-1;
  144. 	lazy=(int *)malloc(size*sizeof(int));
  145. 	for(i=0;i<size;i++) lazy[i]=0;
  146. 	return lazy;
  147. }
  148.  
  149. int main(void)
  150. {
  151. 	int A[]={1,2,6,7,3,4};
  152. 	int *st,*lazy,n=6;
  153. 	st= construct_st(A,n);
  154. 	lazy=construct_lazy(n);
  155. 	int i;
  156. 	int x= (int)((ceil)(log2(n)));
  157. 	int size= 2*(int)pow(2,x)-1;
  158.  
  159. 	printf("Initially Constructed Segment Tree : ");
  160. 	for(i=0;i<size;i++)
  161. 	{
  162. 		printf("%d ",st[i]);
  163. 	}
  164.  
  165. 	int s,e;
  166. 	s=1;
  167. 	e=3;
  168. 	printf("\nSum is %d\n",get_sum(st,lazy,n,s,e));
  169. 	update_val(A,lazy,n,2,4,10,st);
  170. 	printf("Updated sum is %d\n",get_sum(st,lazy,n,s,e));
  171. 	update_val(A,lazy,n,1,2,24,st);
  172. 	printf("Second Updated sum is %d\n",get_sum(st,lazy,n,s,e));
  173. 	return 0;
  174. }
  175.  
  176.  
Success #stdin #stdout 0s 2296KB
comments (?)
stdin
copy 


			

					
			
			

				
	
		
		
	
		
		 stdout
					

				
				 copy
			

			
	

		
Initially Constructed Segment Tree : 23 9 14 3 6 10 4 1 2 0 0 7 3 0 0 
Sum is 15
Updated sum is 22
Second Updated sum is 58


	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/kZsJ0E
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C (gcc 8.3)

					

					

						
created:
								
						
8 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!