C++ Program to Implement Segment Tree

«
»
This C++ program displays the implementation of Segment Tree, a tree data structure for storing intervals, or segments.

Here is the source code of the C++ program to display the sum of the elements in the specified range on giving an array of integers as input. 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 Segment Tree
  3.  */
  4. #include<iostream>
  5. #include <stdio.h>
  6. #include <math.h>
  7. #include<conio.h>
  8. using namespace std;
  9. int getMid(int s, int e)
  10. {
  11.     return s + (e - s) / 2;
  12. }
  13.  
  14. int getSumUtil(int *st, int ss, int se, int qs, int qe, int index)
  15. {
  16.     if (qs <= ss && qe >= se)
  17.         return st[index];
  18.     if (se < qs || ss > qe)
  19.         return 0;
  20.     int mid = getMid(ss, se);
  21.     return getSumUtil(st, ss, mid, qs, qe, 2 * index + 1) + getSumUtil(st, mid + 1, se, qs, qe, 2 * index + 2);
  22. }
  23. void updateValueUtil(int *st, int ss, int se, int i, int diff, int index)
  24. {
  25.     if (i < ss || i > se)
  26.         return;
  27.     st[index] = st[index] + diff;
  28.     if (se != ss)
  29.     {
  30.         int mid = getMid(ss, se);
  31.         updateValueUtil(st, ss, mid, i, diff, 2 * index + 1);
  32.         updateValueUtil(st, mid+1, se, i, diff, 2 * index + 2);
  33.     }
  34. }
  35. void updateValue(int arr[], int *st, int n, int i, int new_val)
  36. {
  37.     if (i < 0 || i > n-1)
  38.     {
  39.         cout<<"Invalid Input";
  40.         return;
  41.     } 
  42.     int diff = new_val - arr[i];
  43.     arr[i] = new_val;
  44.     updateValueUtil(st, 0, n - 1, i, diff, 0);
  45. }
  46. int getSum(int *st, int n, int qs, int qe)
  47. {
  48.     if (qs < 0 || qe > n-1 || qs > qe)
  49.     {
  50.         cout<<"Invalid Input"<<endl;
  51.         return -1;
  52.     }
  53.     return getSumUtil(st, 0, n - 1, qs, qe, 0);
  54. }
  55. int constructSTUtil(int arr[], int ss, int se, int *st, int si)
  56. {
  57.     if (ss == se)
  58.     {
  59.         st[si] = arr[ss];
  60.         return arr[ss];
  61.     }
  62.     int mid = getMid(ss, se);
  63.     st[si] =  constructSTUtil(arr, ss, mid, st, si*2+1) + constructSTUtil(arr, mid + 1, se, st, si*2+2);
  64.     return st[si];
  65. }
  66.  
  67. int *constructST(int arr[], int n)
  68. {
  69.     int x = (int)(ceil(log2(n))); 
  70.     int max_size = 2 * (int)pow(2, x) - 1; 
  71.     int *st = new int[max_size];
  72.     constructSTUtil(arr, 0, n - 1, st, 0);
  73.     return st;
  74. }
  75.  
  76. int main()
  77. {
  78.     int arr[] = {1, 3, 5, 7, 9, 11};
  79.     int n = sizeof(arr) / sizeof(arr[0]);
  80.     int *st = constructST(arr, n);
  81.     cout<<"Sum of values in given range:"<<getSum(st, n, 1, 3)<<endl;
  82.     updateValue(arr, st, n, 1, 10);
  83.     cout<<"Updated sum of values in given range:"<<getSum(st, n, 1, 3);
  84.     getch();
  85. }

advertisement
Output
Sum of values in given range:15
Updated sum of values in given range:22

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