Range Minimum query using Naive algorithm [O(1) update + O(N) query]

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....N-1].

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-:

1. Compute the minimum element in the range (l,r)=(2,5).
2. Update the value at index 3 to '0'.
3. Compute the minimum element in the range (l,r)=(2,5).

Answers-:

1. Minimum element in the index range (2,5) is '3'
2. 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:

• Naive algorithm

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

• Square Root decomposition

  • query: O(square-root of N)
  • update: O(1)

• Segment tree

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

• Fenwick tree

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

• Sparse tree

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

• Cartesian Tree and Farach-Colton 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.