fork download
copy 
  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. using namespace std;
  11.  
  12. const int N = 6;
  13. int seg[2*N-1];
  14.  
  15. int construct (int arr[], int sb, int se, int si) {
  16.     if (sb == se) {
  17.         seg[si] = arr[sb];
  18.     } else {
  19.       int mid = (sb + se)/2;
  20.       seg[si] = construct(arr, sb, mid, 2*si + 1) +
  21.   construct(arr, mid+1, se, 2*si + 2);
  22.    }
  23.     return seg[si];
  24. }
  25.  
  26. int getSum(int sb, int se, int x, int y, int i) {
  27.     if (sb > y || se < x) {
  28.        return 0;
  29.     } else if (sb >= x && se <= y) {
  30.        return seg[i];
  31.     } else {
  32.        int mid = (sb+se)/2;
  33.        return getSum(sb, mid, x, y, 2*i + 1) + getSum(mid+1, se, x, y, 2*i + 2);
  34.     }
  35. }
  36.  
  37. void update (int sb, int se, int idx, int diff, int i) {
  38.   if (idx < sb || idx > se) {
  39.     return;
  40.   }
  41.   seg[i] += diff;
  42.   if (sb != se) {
  43.     int mid = (sb+se)/2;
  44.     update(sb, mid, idx, diff, (2*i + 1));
  45.     update(mid+1, se, idx, diff, (2*i + 2));
  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<<"Sum in the range:"<<endl;
  57.     cout<<"x = 0, y = 2: "<<getSum(0, N-1, 0, 2, 0)<<endl;
  58.     cout<<"x = 3, y = 4: "<<getSum(0, N-1, 3, 4, 0)<<endl;
  59.     cout<<"Update index 3, from 7 to 1"<<endl;
  60.     int diff = 1 - arr[3];
  61.     update(0, N-1, 3, diff, 0);
  62.     cout<<"x = 2, y = 5: "<<getSum(0, N-1, 2, 5, 0)<<endl;
  63.     cout<<"Update index 5, from 11 to 2"<<endl;
  64.     diff = 2 - arr[5];
  65.     update(0, N-1, 5, diff, 0);
  66.     cout<<"x = 3, y = 5: "<<getSum(0, N-1, 3, 5, 0)<<endl;
  67.     cout<<"x = 0, y = 5: "<<getSum(0, N-1, 0, 5, 0)<<endl;
  68.  
  69.     return 0;
  70. }
  71.  
Success #stdin #stdout 0s 5672KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Sum in the range:
x = 0, y = 2: 6
x = 3, y = 4: 16
Update index 3, from 7 to 1
x = 2, y = 5: 23
Update index 5, from 11 to 2
x = 3, y = 5: 12
x = 0, y = 5: 18
https://ideone.com/V0YBDk
language:
C++14 (gcc 8.3)
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!