Range Tree in C++ - Sanfoundry

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.

```
/*
```
```
 * C++ Program to Implement Range Tree
```
```
 */
```
```
#include<stdio.h>
```
```
#include<math.h>
```
```
#include<limits.h>
```
```
#include<conio.h>
```
```
#include<iostream>
```
```
int minVal(int x, int y)
```
```
{
```
```
    return (x < y) ? x: y;
```
```
}
```
```
int getMid(int s, int e)
```
```
{
```
```
    return s + (e - s) / 2;
```
```
}
```

int RMQUtil(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 INT_MAX;
```
```
 
```
```
    int mid = getMid(ss, se);
```

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

```
}
```
```
int RMQ(int *st, int n, int qs, int qe)
```
```
{
```
```
    if (qs < 0 || qe > n-1 || qs > qe)
```
```
    {
```
```
        cout<<"Invalid Input";
```
```
        return -1;
```
```
    }
```

    return RMQUtil(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] =  minVal(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, 2, 7, 9, 11};
```
```
    int n = sizeof(arr)/sizeof(arr[0]);
```
```
    int *st = constructST(arr, n);
```
```
    int qs = 1;
```
```
    int qe = 5;
```

    cout<<"Minimum of values in range is =",qs, qe, RMQ(st, n, qs, qe);

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

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

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

Subscribe Now: Data Structures in C++ Newsletter | Important Subjects Newsletters

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

« Prev - C++ Program to Implement Fusion Tree

» Next - C++ Program to Implement Red Black Tree

Next Steps:

Get Free Certificate of Merit in Data Structure I
Participate in Data Structure I Certification Contest
Become a Top Ranker in Data Structure I
Take Data Structure I Tests
Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Related Posts:

Recommended Articles: