C++ Program to Implement Range Tree

«
»
This C++ program implements the range tree, a range tree is an ordered tree data structure to hold a list of points.

Here is the source code of the C++ program to display the minimum of values present in a pre-specified range. This C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is given below.

  1. /*
  2.  * C++ Program to Implement Range Tree
  3.  */
  4. #include<stdio.h>
  5. #include<math.h>
  6. #include<limits.h>
  7. #include<conio.h>
  8. #include<iostream>
  9. int minVal(int x, int y)
  10. {
  11.     return (x < y) ? x: y;
  12. }
  13. int getMid(int s, int e)
  14. {
  15.     return s + (e - s) / 2;
  16. }
  17. int RMQUtil(int *st, int ss, int se, int qs, int qe, int index)
  18. {
  19.     if (qs <= ss && qe >= se)
  20.         return st[index];
  21.  
  22.     if (se < qs || ss > qe)
  23.         return INT_MAX;
  24.  
  25.     int mid = getMid(ss, se);
  26.     return minVal(RMQUtil(st, ss, mid, qs, qe, 2*index+1), RMQUtil(st, mid+1, se, qs, qe, 2*index+2));
  27. }
  28. int RMQ(int *st, int n, int qs, int qe)
  29. {
  30.     if (qs < 0 || qe > n-1 || qs > qe)
  31.     {
  32.         cout<<"Invalid Input";
  33.         return -1;
  34.     }
  35.     return RMQUtil(st, 0, n-1, qs, qe, 0);
  36. }
  37. int constructSTUtil(int arr[], int ss, int se, int *st, int si)
  38. {
  39.     if (ss == se)
  40.     {
  41.         st[si] = arr[ss];
  42.         return arr[ss];
  43.     }
  44.     int mid = getMid(ss, se);
  45.     st[si] =  minVal(constructSTUtil(arr, ss, mid, st, si * 2 + 1), constructSTUtil(arr, mid + 1, se, st, si * 2 + 2));
  46.     return st[si];
  47. }
  48. int *constructST(int arr[], int n)
  49. {
  50.     int x = (int)(ceil(log2(n)));
  51.     int max_size = 2 * (int)pow(2, x) - 1;
  52.     int *st = new int[max_size];
  53.     constructSTUtil(arr, 0, n - 1, st, 0);
  54.     return st;
  55. }
  56.  
  57. int main()
  58. {
  59.     int arr[] = {1, 3, 2, 7, 9, 11};
  60.     int n = sizeof(arr)/sizeof(arr[0]);
  61.     int *st = constructST(arr, n);
  62.     int qs = 1;
  63.     int qe = 5;
  64.     cout<<"Minimum of values in range is =",qs, qe, RMQ(st, n, qs, qe);
  65.     getch();
  66. }

advertisement
Output
Minimum of values in range [1, 5] is = 2

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn