Range Minimum query using Naive algorithm [O(1) update + O(N) query]
Sign up for FREE 1 month of Kindle and read all our books for free.
Get FREE domain for 1st year and build your brand new site
Reading time: 25 minutes  Coding time: 10 minutes
In the range minimum query problem, we have to optimize two queries. One query is to find minimum value in a given range and the other query is to update an element at a given index. The update operation changes the minimum element in involved ranges which makes this a difficult problem.
In this article, we will look into the basic approach (naive) to solve this problem which is able to perform the update query in constant time O(1) and range query in linear time O(N).
Problem Statement
Compute the minimum element in the given array within index ranges given by the user. In this article we are going to explain the naive algorithm to solve range minimum queries.
We are given an array A[0....N1].
The problem consist of two parts:

Update(i,val): In this part we have to update an element at index i with val

Query(l,r): In this part we have to return the minimum value between index βlβ and βrβ inclusive
Example:
Given an array A[] = {1,4,3,5,6,7}.
Tasks:
 Compute the minimum element in the range (l,r)=(2,5).
 Update the value at index 3 to '0'.
 Compute the minimum element in the range (l,r)=(2,5).
Answers:
 Minimum element in the index range (2,5) is '3'
 Minimum element in the index range (2,5) after updating element at index 3 is '0'
Naive algorithm
In the naive approach, we can execute the update query in constant time which is efficient and the best case but the query operation takes linear time O(N) which is slow depending upon:
 the number of elements (N) we are handling
 the number of queries executed.
Let us see how the two operations are done in Naive algorithm:
Update operation in O(1)
Step 1: Find the index and update the value at given index. This is efficient as in array we can directly access an element at any given index and update it. If we are dealing with linked list, then this step slows down to linear time O(N).
Pseudocode of update():
update(array, index, new_value)
{
array[index] = new_value;
}
Query operation in O(N)
In this approach, the idea is to traverse all elements in the range and keep a track of the minimum element. This is done in linear time O(N) as it is a simple traversal.
 Step 1: Assign βINT MAXβ to a variable βminβ
 Step 2: Loop from index βlβ to βrβ both inclusive
 Step 3: If A[i] is less than min, goto step 4
 Step 4: min=A[i]
 Step 5: min is the answer
Pseudocode of query():
int query(int a[],int l,int r)
{
int min=INT_MAX;
for(int i=l;i<=r;i++)
{
if(a[i]<min)
{
min=a[i];
}
}
return min;
}
Time Complexity:

Query: O(N)

Update: O(1)
C++ Implementation:
#include <bits/stdc++.h>
using namespace std;
int query(int a[],int l,int r)
{
int min=INT_MAX;
for(int i=l;i<=r;i++)
{
if(a[i]<min)
{
min=a[i];
}
}
return min;
}
void update(int a[], int index,int val)
{
a[index]=val;//value at index replaced with 'val'
}
int main()
{
int a[]={4,5,3,2,4,6,6,3};
cout<<"query(3,6) before update :"<<query(a,3,6)<<"\n";
update(a,3,0);
cout<<"query(3,6) after update :"<<query(a,3,6)<<"\n";
return 0;
}
Output:
query(3,6) before update :2
query(3,6) after update :0
Different ways to solve this problem:
There are different ways to solve this problem:

 query in O(N)
 update in O(1)

Square Root decomposition
 query: O(squareroot of N)
 update: O(1)

 query: O(log N)
 update: O(log N)

 query: O(log N)
 update: O(N log N)

 query: O(1)
 update: O(N log N)

Cartesian Tree and FarachColton and Bender algorithm
 query: O(1)
 update: O(N)
With this, you should have a strong basic knowledge of this problem. We will work over improving this with other efficient approaches in our other articles. Enjoy.