• • In this blog post we are going to learn how to write c program for range minimum query.

## What is range minimum query?

The range minimum query is a problem of finding minimum value in a given range. For example give an array of integers {1,2,4,8,5,3,2,0,9} what is minimum value in sub-array from index 2 to 5 ?

The minimum value in sub-array (position from 2 to 5) is 3 and position is 5th index.

## Naive c program for range minimum query

It is very easy to find minimum in a given range. simply compare each elements in a given range and print final minimum. Let see simple c program.

```#include <stdio.h>

int RMQ(int arr [], int range_start, int range_end)
{
int minimum = arr [ range_start];

for (int i = range_start + 1; i <= range_end; i++)
{
if (minimum > arr [ i])
{
minimum = arr [ i];
}
}
return minimum;
}
int main()
{
int arr [ 9] =
{ 1, 2, 4, 8, 5, 3, 2, 0, 9 };
int ans = RMQ(arr, 2, 5);
printf("%d\n", ans);
return 0;
}
```

The algorithmic complexity of above solution is O(n)in worst case. Can we solve this problem with less than O(n) complexity.

## Segment tree based c program for range minimum

Let us discuss what is segment tree? Segment tree is a tree like data structure which stores information about intervals. For example for our array of integers {1,2,4,8,5,3,2,0,9} , the segment tree will stores minimum between intervals or range.

To reduce time complexity for finding minimum between a given range ( sub-array) we will pre-process our array {1,2,4,8,5,3,2,0,9} and build a segment tree.

## How to build segment tree from given array of integers

Let us see segment tree for array {1,2,4,8,5,3,2,0,9} 1. Root of the segment tree contains minimum value in entire range [0,8].
2. Each of the segment is divided into two segments, one segment contains information about interval from i to ((i + j)/2) and other one contains information about interval ((i+j)/2+1) to j.
3. The division continue till each each segment contains only one element i.e i == j.
4. The building of segment tree has O(NlogN) complexity.

### what could be maximum size of segment tree if we represent segment tree based on array?

From  above diagram of segment tree , each segment is divided into two segments until each segment becomes one. In this way we can write code like below to calculate require size of segment tree

```int getRequireSizeOfSegmTree(int arr_size)
{
int size = 1;
for (; size <= arr_size; size <<= 1);
return size + 1;
}```

So if the size of an array is N the required size could be 2N -1.

Now we have built our segment tree. Let us see how to query from segment tree

1. Let us suppose we want a minimum value from range x, to y.
2. Check if the range (x,y) is valid , it might be outside of the entire range.
3. if range (x,y) is valid search in left and right child and return minimum of left and right.

### Sample implementation

```#include <stdio.h>
#include<limits.h>
#include<malloc.h>

int getRequireSizeOfSegmTree(int arr_size)
{
int size = 1;
for (; size <= arr_size; size <<= 1)
;
return size + 1;
}

void build_seg_tree(int segmentTree [], int arr [], int start, int end,
int current)
{

if (start == end)
{
segmentTree [ current] = arr [ start];
return;
}

int mid = (start + end) / 2;
int leftchild = 2 * current + 1;
int rightchild = 2 * current + 2;

build_seg_tree(segmentTree, arr, start, mid, leftchild);
build_seg_tree(segmentTree, arr, mid + 1, end, rightchild);

if (segmentTree [ leftchild] < segmentTree [ rightchild])
{
segmentTree [ current] = segmentTree [ leftchild];
}
else
{
segmentTree [ current] = segmentTree [ rightchild];
}
}

int RMQHelper(int segmentTree [], int qs, int qe, int start, int end,
int current_pos)
{

//if the current range is invalid
//the query interval return -1
if (qs > end || qe < start) return INT_MAX;

//if the query interval is within range
if (start >= qs && end <= qe) return segmentTree [ current_pos];

// find middle
int mid = (start + end) / 2;
//search in left
int left = RMQHelper(segmentTree, qs, qe, start, mid, 2 * current_pos + 1);
//search in right
int right = RMQHelper(segmentTree, qs, qe, mid + 1, end,
2 * current_pos + 2);

// return minimum
if (left > right) return right;
else
return left;
}

int RMQ(int segmentTree [], int qs, int qe, int size)
{
return RMQHelper(segmentTree, qs, qe, 0, size, 0);
}

void test_RMQ(int segmentTree [], int arr_length, int arr [])
{
if (RMQ(segmentTree, 0, 0, arr_length) == arr [ 0]) printf("0 0 PASS\n");
else
printf("0 0 FAIL\n");
if (RMQ(segmentTree, 1, 1, arr_length) == arr [ 1]) printf("1 1 PASS\n");
else
printf("1 1 FAIL\n");
if (RMQ(segmentTree, 2, 2, arr_length) == arr [ 2]) printf("2 2 PASS\n");
else
printf("2 2 FAIL\n");
if (RMQ(segmentTree, 3, 3, arr_length) == arr [ 3]) printf("3 3 PASS\n");
else
printf("3 3 FAIL\n");
if (RMQ(segmentTree, 4, 4, arr_length) == arr [ 4]) printf("4 4 PASS\n");
else
printf("4 4 FAIL\n");
if (RMQ(segmentTree, 5, 5, arr_length) == arr [ 5]) printf("5 5 PASS\n");
else
printf("5 5 FAIL\n");
if (RMQ(segmentTree, 6, 6, arr_length) == arr [ 6]) printf("6 6 PASS\n");
else
printf("6 6 FAIL\n");

if (RMQ(segmentTree, 7, 7, arr_length) == arr [ 7]) printf("7 7 PASS\n");
else
printf("7 7 FAIL\n");

if (RMQ(segmentTree, 8, 8, arr_length) == arr [ 8]) printf("8 8 PASS\n");
else
printf("8 8 FAIL\n");

if (RMQ(segmentTree, 9, 9, arr_length) == INT_MAX) printf("9 9 PASS\n");
else
printf("9 9 FAIL\n");

if (RMQ(segmentTree, 0, 1, arr_length) == arr [ 0]) printf("0 1 PASS\n");
else
printf("0 1 FAIL\n");

if (RMQ(segmentTree, 2, 5, arr_length) == arr [ 5]) printf("2 5 PASS\n");
else
printf("2 5 FAIL\n");

if (RMQ(segmentTree, 4, 6, arr_length) == arr [ 6]) printf("4 6 PASS\n");
else
printf("4 6 FAIL\n");

if (RMQ(segmentTree, 3, 7, arr_length) == arr [ 7]) printf("3 7 PASS\n");
else
printf("3 7 FAIL\n");
if (RMQ(segmentTree, 1, 3, arr_length) == arr [ 1]) printf("1 3 PASS\n");
else
printf("1 3 FAIL\n");

if (RMQ(segmentTree, 0, 8, arr_length) == arr [ 7]) printf("0 8 PASS\n");
else
printf("0 8 FAIL\n");
}

int main()
{
int arr [] =
{ 1, 2, 4, 8, 5, 3, 2, 0, 9 };
int arr_size = sizeof(arr) / sizeof(arr [ 0]);
int segm_tree_size = getRequireSizeOfSegmTree(arr_size);
int *segmtree = (int*) malloc(sizeof(int) * segm_tree_size);
build_seg_tree(segmtree, arr, 0, arr_size - 1, 0);
// test
test_RMQ(segmtree, arr_size - 1, arr);
return 0;
}
```

Ref:

https://en.wikipedia.org/wiki/Range_minimum_query