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. }

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

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

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.