fork download 
  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.  
  17. //This method build our segment tree ie. the array seg
  18. int construct (int arr[], int sb, int se, int si) {
  19.  
  20.   //Base case (only 1 element)
  21.   if (sb == se) {
  22.     seg[si] = arr[sb];
  23.   } else {
  24.     int mid = (sb+se)/2;   //Dividing given range in two equal halves
  25.  
  26.     seg[si] = min((construct(arr, sb, mid, 2*si + 1)), 
  27.                            (construct(arr, mid+1, se, 2*si + 2)));
  28.   }
  29.  
  30.   return seg[si];
  31. }
  32.  
  33. int getMin(int sb, int se, int x, int y, int i) {
  34.  
  35.  //Base case: Out of bound range
  36.  if (sb > y || se < x) {
  37.    return INT_MAX;
  38.  } else if (sb >= x && se <= y) {
  39.    return seg[i]; //Node in permissible range, send the value of internal node (i). 
  40.  } else {
  41.    int mid = (sb+se)/2;
  42.    return min((getMin(sb, mid, x, y, 2*i + 1)),     // Checking children nodes [(2*i+1), (2*i+2)]
  43.               (getMin(mid+1, se, x, y, 2*i + 2)));
  44.  }
  45.  
  46. }
  47.  
  48.  
  49. int main() {
  50.     int arr[] = {1, 3, 2, 7, 9, 11};
  51.  
  52.     // Constructing segment tree (preprocessing)
  53.     construct(arr, 0, N-1, 0);
  54.  
  55.     // Print minimum value in arr[qs..qe]
  56.     cout<<"Minimum element in the range:"<<endl;
  57.     cout<<"x = 1, y = 5: "<<getMin(0, N-1, 1, 5, 0)<<endl;
  58.     cout<<"x = 0, y = 3: "<<getMin(0, N-1, 0, 3, 0)<<endl;
  59.     cout<<"x = 3, y = 5: "<<getMin(0, N-1, 3, 5, 0)<<endl;
  60.     cout<<"x = 0, y = 4: "<<getMin(0, N-1, 0, 4, 0)<<endl;
  61.  
  62.     return 0;
  63. }
  64.  
Success #stdin #stdout 0.01s 5432KB
comments (?)
stdin 
Standard input is empty
stdout 
Minimum element in the range:
x = 1, y = 5: 2
x = 0, y = 3: 1
x = 3, y = 5: 7
x = 0, y = 4: 1
https://ideone.com/a1tmOc
language:
C++ 4.3.2 (gcc-4.3.2)
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!