Segment Tree in C++ - Sanfoundry

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.

```
/*
```

 * C++ Program to Implement Segment Tree

```
 */
```
```
#include<iostream>
```
```
#include <stdio.h>
```
```
#include <math.h>
```
```
#include<conio.h>
```
```
using namespace std;
```
```
int getMid(int s, int e)
```
```
{
```
```
    return s + (e - s) / 2;
```
```
}
```
```
 
```

int getSumUtil(int *st, int ss, int se, int qs, int qe, int index)

```
{
```
```
    if (qs <= ss && qe >= se)
```
```
        return st[index];
```
```
    if (se < qs || ss > qe)
```
```
        return 0;
```
```
    int mid = getMid(ss, se);
```

    return getSumUtil(st, ss, mid, qs, qe, 2 * index + 1) + getSumUtil(st, mid + 1, se, qs, qe, 2 * index + 2);

```
}
```

void updateValueUtil(int *st, int ss, int se, int i, int diff, int index)

```
{
```
```
    if (i < ss || i > se)
```
```
        return;
```
```
    st[index] = st[index] + diff;
```
```
    if (se != ss)
```
```
    {
```
```
        int mid = getMid(ss, se);
```

        updateValueUtil(st, ss, mid, i, diff, 2 * index + 1);

        updateValueUtil(st, mid+1, se, i, diff, 2 * index + 2);

```
    }
```
```
}
```

void updateValue(int arr[], int *st, int n, int i, int new_val)

```
{
```
```
    if (i < 0 || i > n-1)
```
```
    {
```
```
        cout<<"Invalid Input";
```
```
        return;
```
```
    } 
```
```
    int diff = new_val - arr[i];
```
```
    arr[i] = new_val;
```

    updateValueUtil(st, 0, n - 1, i, diff, 0);

```
}
```

int getSum(int *st, int n, int qs, int qe)

```
{
```
```
    if (qs < 0 || qe > n-1 || qs > qe)
```
```
    {
```
```
        cout<<"Invalid Input"<<endl;
```
```
        return -1;
```
```
    }
```

    return getSumUtil(st, 0, n - 1, qs, qe, 0);

```
}
```

int constructSTUtil(int arr[], int ss, int se, int *st, int si)

```
{
```
```
    if (ss == se)
```
```
    {
```
```
        st[si] = arr[ss];
```
```
        return arr[ss];
```
```
    }
```
```
    int mid = getMid(ss, se);
```

    st[si] =  constructSTUtil(arr, ss, mid, st, si*2+1) + constructSTUtil(arr, mid + 1, se, st, si*2+2);

```
    return st[si];
```
```
}
```
```
 
```
```
int *constructST(int arr[], int n)
```
```
{
```
```
    int x = (int)(ceil(log2(n))); 
```

    int max_size = 2 * (int)pow(2, x) - 1;

```
    int *st = new int[max_size];
```

    constructSTUtil(arr, 0, n - 1, st, 0);

```
    return st;
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int arr[] = {1, 3, 5, 7, 9, 11};
```

    int n = sizeof(arr) / sizeof(arr[0]);

```
    int *st = constructST(arr, n);
```

    cout<<"Sum of values in given range:"<<getSum(st, n, 1, 3)<<endl;

```
    updateValue(arr, st, n, 1, 10);
```

    cout<<"Updated sum of values in given range:"<<getSum(st, n, 1, 3);

```
    getch();
```
```
}
```

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

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

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

« Prev - C++ Program to Implement ScapeGoat Tree

» Next - C++ Program to Implement Splay Tree

Related Posts:

Check Programming Books
Practice Design & Analysis of Algorithms MCQ
Practice Computer Science MCQs
Check Data Structure Books
Check Computer Science Books

Recommended Articles: