//
//  main.cpp
//  Segment Tree
//
//  Created by Himanshu on 22/08/21.
//

#include <iostream>
#include <math.h>
#include <climits>
using namespace std;

const int N = 6;
int seg[2*N-1];

int construct (int arr[], int sb, int se, int si) {
  if (sb == se) {
      seg[si] = arr[sb];
  } else {
    int mid = (sb+se)/2;
    seg[si] = min((construct(arr, sb, mid, 2*si + 1)),
(construct(arr, mid+1, se, 2*si + 2)));
 }
  return seg[si];
}

int getMin(int sb, int se, int x, int y, int i) {
 if (sb > y || se < x) {
   return INT_MAX;
 } else if (sb >= x && se <= y) {
   return seg[i];
 } else {
   int mid = (sb+se)/2;
   return min((getMin(sb, mid, x, y, 2*i + 1)),
(getMin(mid+1, se, x, y, 2*i + 2)));
 }
}

void update (int arr[], int sb, int se, int idx, int val, int i) {
  //Base case: index not in the range
  if (idx < sb || idx > se) {
    return;
  } //index to be changed
    else if (sb == se) {
    arr[idx] = val;
    seg[i] = val;
  } else {
    int mid = (sb+se)/2;
    if (idx >= sb && idx <= mid) { 
      update(arr, sb, mid, idx, val, 2*i + 1);
    } else {
      update(arr, mid+1, se, idx, val, 2*i + 2); 
    } 
   seg[i] = min(seg[2*i + 1], seg[2*i + 2]);
  }
}

int main() {
    int arr[] = {1, 3, 2, 7, 9, 11};
    
    // Constructing segment tree (preprocessing)
    construct(arr, 0, N-1, 0);

    // Print minimum value in arr[qs..qe]
    cout<<"Minimum element in the range:"<<endl;
    cout<<"x = 1, y = 5: "<<getMin(0, N-1, 1, 5, 0)<<endl;
    cout<<"x = 0, y = 3: "<<getMin(0, N-1, 0, 3, 0)<<endl;
    cout<<"Update index 3, from 7 to 1"<<endl;
    update(arr, 0, N-1, 3, 1, 0);
    cout<<"x = 2, y = 5: "<<getMin(0, N-1, 2, 5, 0)<<endl;
    cout<<"Update index 0, from 1 to 5"<<endl;
    update(arr, 0, N-1, 0, 5, 0);
    cout<<"x = 0, y = 2: "<<getMin(0, N-1, 0, 2, 0)<<endl;
    
    return 0;
}