fork download
copy 
  1. //Query : Find minimum in range
  2. //Update: Add v to all elements in range
  3.  
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. #define INF 2e9
  9. #define NMAX 100010
  10. #define TMAX ((1<<18)+10)
  11.  
  12. int A[NMAX];
  13.  
  14. int tree[TMAX];
  15. int incr[TMAX];
  16.  
  17. int N;
  18.  
  19. inline int left(int x){ return x*2+1; }
  20. inline int right(int x) { return x*2+2; }
  21. inline int parent(int x){ return (x+1)/2-1; }
  22.  
  23. inline void push(int node, int node2){
  24. 	incr[node2] += incr[node];
  25. 	tree[node2] += incr[node];
  26. }
  27.  
  28.  
  29.  
  30. void init(int node, int s, int e){
  31.  
  32. 	if(s == e){
  33. 		incr[node] = 0;
  34. 		tree[node] = A[s];
  35. 		return;
  36. 	}
  37.  
  38. 	int l,r,m;
  39. 	l = left(node), r = right(node) ,m = (s+e)/2;
  40.  
  41. 	init(l,s,m);
  42. 	init(r,m+1,e);
  43.  
  44. 	incr[node] =0;
  45. 	tree[node] = min(tree[l],tree[r]);
  46. }
  47.  
  48.  
  49. int query(int node, int s, int e, int i, int j){
  50.  
  51. 	if(s > j || e < i) return INF;
  52. 	if(s >= i && e <= j) return tree[node];
  53.  
  54. 	int l,r,m;
  55. 	l = left(node), r = right(node), m = (s+e)/2;
  56.  
  57. 	push(node,l);
  58. 	push(node,r);
  59. 	incr[node] =0;
  60.  
  61. 	return min(query(l,s,m,i,j),query(r,m+1,e,i,j));
  62. }
  63.  
  64.  
  65.  
  66. void update(int node, int s, int e, int i, int j, int val){
  67. 	if(s > j || e< i) return;
  68. 	if(s >= i && e <= j) {
  69. 		tree[node] += val;
  70. 		incr[node] += val;
  71. 		return;
  72. 	}
  73.  
  74. 	int l,r,m;
  75. 	l = left(node), r = right(node), m = (s+e)/2;
  76.  
  77. 	push(node,l);
  78. 	push(node,r);
  79. 	incr[node] =0;
  80.  
  81. 	update(l,s,m,i,j,val);
  82. 	update(r,m+1,e,i,j,val);
  83.  
  84. 	tree[node] = min(tree[l],tree[r]);
  85. }
  86.  
  87.  
  88. //calling query and init and update
  89.  
  90. void init(){
  91. 	init(0,0,N-1);
  92. }
  93.  
  94. int query(int i, int j){
  95. 	return query(0,0,N-1,i,j);
  96. }
  97.  
  98. void update(int i, int j, int val){
  99. 	update(0,0,N-1,i,j,val);
  100. }
  101.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/usr/lib/gcc/i586-linux-gnu/5/../../../i386-linux-gnu/crt1.o: In function `_start':
(.text+0x18): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/7Sbdez
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

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!