the build function in segment tree : ↵
↵
~~~~~↵
void build(intsid = 1 , ,int el = n , 0,int pr = 1n){ ↵
if(s == e) {↵
seg[p] = 1 ;↵
if(r - l < 2){ // l + 1 == r↵
s[id] = a[l];↵
return ; ↵
}↵
build(s , (s + e)/2 , 2 * p) ;↵
build((s + e)/2 + 1 , e , 2 }↵
int mid = (l+r)/2;↵
build(id * 2, l, mid);↵
build(id * 2 + 1, mid, r);↵
s[id] = s[id * 2] + s[id *p2 + 1)];↵
}↵
~~~~~↵
↵
divide and conquer algorithm to find maximum element in array : ↵
↵
~~~~~↵
int Max(int s = 1 , int e = n){↵
if(s == e) return arr[s] ; ↵
int choice1 = arr[s] , choice2 = arr[e] ; ↵
choice1 = max( choice1 , Max( s , (s + e)/2 ) ; ↵
choice2 = max( choice2 , Max( (s + e)/2 + 1 , e ) ;↵
return max(choice1 , choice2) ; ↵
}↵
~~~~~↵
↵
why the complexity of the first function is O( n * log(n) ) And the second is O(n) ↵
thanks for your help :D ↵
↵
~~~~~↵
void build(int
seg[p] = 1 ;↵
s[id] = a[l];↵
return ;
build(s , (s + e)/2 , 2 * p) ;↵
build((s + e)/2 + 1 , e , 2
int mid = (l+r)/2;↵
build(id * 2, l, mid);↵
build(id * 2 + 1, mid, r);↵
s[id] = s[id * 2] + s[id *
}↵
~~~~~↵
↵
divide and conquer algorithm to find maximum element in array : ↵
↵
~~~~~↵
int Max(int s = 1 , int e = n){↵
if(s == e) return arr[s] ; ↵
int choice1 = arr[s] , choice2 = arr[e] ; ↵
choice1 = max( choice1 , Max( s , (s + e)/2 ) ; ↵
choice2 = max( choice2 , Max( (s + e)/2 + 1 , e ) ;↵
return max(choice1 , choice2) ; ↵
}↵
~~~~~↵
↵
why the complexity of the first function is O( n * log(n) ) And the second is O(n) ↵
thanks for your help :D ↵
