ITMO Academy: pilot course » Segment Tree, part 1 » Step 1 » Practice B. Segment Tree for the Minimum Solution

 

Problem Link : https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/problem/b

Solution in C++:

1. /// Author : AH_Tonmoy
2. #include <bits/stdc++.h>
3. using namespace std;
4. const int N = 1e5 + 9 , inf = 1e9+ 9 ;
5. using ll = long long ;
6. ll a[N] ;
7. ll t[N*4] ;
8. void build( ll node ,ll b , ll e ) {
9. if ( b == e ){
10. t[node] = a[b] ;
11. return ;
12. }
13. ll l = 2 * node , r = 2 * node + 1 ;
14. ll mid = ( b + e )/2 ;
15. build( l , b , mid ) ;
16. build(r , mid + 1 , e) ;
17. t[node] =min( t[l] , t[r] ) ;
18. }
19. ll query( ll node , ll b , ll e , ll i , ll j ){
20. if ( i > e or j < b) return inf ;
21. if ( i <= b and e <= j){
22. return t[node] ;
23. }
24. ll l = 2 * node , r = 2 * node + 1 ;
25. ll mid = ( b + e )/2 ;
26. return min(query( l , b , mid , i , j ) , query( r , mid + 1 , e , i , j ) );
27. }
28. void upd( ll node , ll b , ll e , ll i , ll x) {
29. if ( i < b or i > e ) return ;
30. if( b == e and b == i ) {
31. t[node] = x ;
32. return ;
33. }
34. ll l = 2 * node , r = 2 * node + 1 ;
35. ll mid = ( b + e )/2 ;
36. upd( l , b , mid , i , x) ;
37. upd( r , mid + 1 , e , i , x) ;
38. t[node] = min(t[l], t[r]) ;
39. }
40. int32_t main() {
41. ios_base::sync_with_stdio(0);
42. cin.tie(0);
43. ll n , m ;
44. cin >> n >> m ;
45. for ( ll i = 0 ; i < n ; i++) {
46. cin >> a[i] ;
47. }
48. build(1,0,n - 1);
49. while ( m --) {
50. ll num , l , r;
51. cin >> num >> l >> r ;
52. if ( num == 1) {
53. upd(1 , 0 , n - 1, l , r ) ;
54. }
55. else
56. cout << query(1 , 0 , n - 1 , l , r - 1 ) <<'\n' ;
57. }
58. return 0 ;
59. }
60.