fork download
copy 
  1. //
  2. //  main.cpp
  3. //  Segment Tree
  4. //
  5. //  Created by Himanshu on 22/08/21.
  6. //
  7.  
  8. #include <iostream>
  9. #include <math.h>
  10. #include <climits>
  11. using namespace std;
  12.  
  13. const int N = 6;
  14. int seg[2*N-1];
  15.  
  16. int construct (int arr[], int sb, int se, int si) {
  17.   if (sb == se) {
  18.       seg[si] = arr[sb];
  19.   } else {
  20.     int mid = (sb+se)/2;
  21.     seg[si] = min((construct(arr, sb, mid, 2*si + 1)),
  22. (construct(arr, mid+1, se, 2*si + 2)));
  23.  }
  24.   return seg[si];
  25. }
  26.  
  27. int getMin(int sb, int se, int x, int y, int i) {
  28.  if (sb > y || se < x) {
  29.    return INT_MAX;
  30.  } else if (sb >= x && se <= y) {
  31.    return seg[i];
  32.  } else {
  33.    int mid = (sb+se)/2;
  34.    return min((getMin(sb, mid, x, y, 2*i + 1)),
  35. (getMin(mid+1, se, x, y, 2*i + 2)));
  36.  }
  37. }
  38.  
  39. void update (int arr[], int sb, int se, int idx, int val, int i) {
  40.   //Base case: index not in the range
  41.   if (idx < sb || idx > se) {
  42.     return;
  43.   } //index to be changed
  44.     else if (sb == se) {
  45.     arr[idx] = val;
  46.     seg[i] = val;
  47.   } else {
  48.     int mid = (sb+se)/2;
  49.     if (idx >= sb && idx <= mid) { 
  50.       update(arr, sb, mid, idx, val, 2*i + 1);
  51.     } else {
  52.       update(arr, mid+1, se, idx, val, 2*i + 2); 
  53.     } 
  54.    seg[i] = min(seg[2*i + 1], seg[2*i + 2]);
  55.   }
  56. }
  57.  
  58. int main() {
  59.     int arr[] = {1, 3, 2, 7, 9, 11};
  60.  
  61.     // Constructing segment tree (preprocessing)
  62.     construct(arr, 0, N-1, 0);
  63.  
  64.     // Print minimum value in arr[qs..qe]
  65.     cout<<"Minimum element in the range:"<<endl;
  66.     cout<<"x = 1, y = 5: "<<getMin(0, N-1, 1, 5, 0)<<endl;
  67.     cout<<"x = 0, y = 3: "<<getMin(0, N-1, 0, 3, 0)<<endl;
  68.     cout<<"Update index 3, from 7 to 1"<<endl;
  69.     update(arr, 0, N-1, 3, 1, 0);
  70.     cout<<"x = 2, y = 5: "<<getMin(0, N-1, 2, 5, 0)<<endl;
  71.     cout<<"Update index 0, from 1 to 5"<<endl;
  72.     update(arr, 0, N-1, 0, 5, 0);
  73.     cout<<"x = 0, y = 2: "<<getMin(0, N-1, 0, 2, 0)<<endl;
  74.  
  75.     return 0;
  76. }
  77.  
Success #stdin #stdout 0s 5664KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Minimum element in the range:
x = 1, y = 5: 2
x = 0, y = 3: 1
Update index 3, from 7 to 1
x = 2, y = 5: 1
Update index 0, from 1 to 5
x = 0, y = 2: 2
https://ideone.com/jngIub
language:
C++14 (gcc 8.3)
created:
2 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!