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. int construct (int arr[], int sb, int se, int si) {
  17.  
  18.   //Base case (only 1 element)
  19.   if (sb == se) {
  20.     seg[si] = arr[sb];
  21.   } else {
  22.     int mid = (sb+se)/2;  
  23.     seg[si] = max((construct(arr, sb, mid, 2*si + 1)), 
  24.                            (construct(arr, mid+1, se, 2*si + 2)));
  25.   }
  26.  
  27.   return seg[si];
  28. }
  29.  
  30. int getMax(int sb, int se, int p, int q, int i) {
  31.  
  32.  //Base case: Out of bound range
  33.  if (sb > q || se < p) {
  34.    return INT_MIN;
  35.  } else if (sb >= p && se <= q) {
  36.    return seg[i]; 
  37.  } else {
  38.    int mid = (sb+se)/2;
  39.    return max((getMax(sb, mid, p, q, 2*i + 1)),  
  40.               (getMax(mid+1, se, p, q, 2*i + 2)));
  41.  }
  42.  
  43. }
  44.  
  45. int main() {
  46.     int arr[] = {1, 3, 2, 7, 9, 11};
  47.  
  48.     // Constructing segment tree (preprocessing)
  49.     construct(arr, 0, N-1, 0);
  50.  
  51.     // Print maximum value in arr[qs..qe]
  52.     cout<<"Maximum element in the range:"<<endl;
  53.     cout<<"p = 1, q = 5: "<<getMax(0, N-1, 1, 5, 0)<<endl;
  54.     cout<<"p = 0, q = 3: "<<getMax(0, N-1, 0, 3, 0)<<endl;
  55.     cout<<"p = 3, q = 5: "<<getMax(0, N-1, 3, 5, 0)<<endl;
  56.     cout<<"p = 0, q = 4: "<<getMax(0, N-1, 0, 4, 0)<<endl;
  57.  
  58.     return 0;
  59. }
  60.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Maximum element in the range:
p = 1, q = 5: 11
p = 0, q = 3: 7
p = 3, q = 5: 11
p = 0, q = 4: 9
https://ideone.com/re7At0
language:
C++14 (gcc 8.3)
created:
36 days 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!