Queries to find the min index in a range [L, R] having at least value ele with updates

Apoorv
Last Updated: May 13, 2022

Problem statement

Given an array input[] of size 'size' with all the integer elements and a two-dimensional array Queries[][] containing queries of the following two types:

 Query 1 is of the type {type, ind, ele} if the value of type is 1, then update the Array's 'ind' Index to 'ele.'

Query 2 is of the type {ele, l, r} find the first index such that the value at that index is greater than equal to at least 'ele' in the range l to r, and if does not exist, then return '-1'.

 

Example 1

Input

Input[] = { 1, 4, 3, 7, 2, 6, 8 }

Size = 7

Query = { { 2, 0, 6 }, 

                { 1, 2, 5 },

                { 4, 0, 6 },

      { 0, 0, 6 } };

Output

1

1

0

Explanation

Query 1: Find the index of first value at least 2 in the range [0, size-1] so in the Array, you can see 1 index of the Array is 4, which is greater than 2; hence for query 1 ans will be 1st index.

Query 2: Update the value at index 2 to 5 because the type is 1 means we have to update, and at index 2 we will update the value with 5, so the updated Array is  { 1, 4, 5, 7, 2, 6, 8 }

Query 3: Find the index of first value at least 4 in the range [0, size-1] so in the Array, you can see 1 index of the Array is 4, which is greater than equal to 4; hence for query 3 ans will be 1st index.

Query 4: Find the index of first value at least 0 in the range [0, size-1] so in the Array, you can see 0 index of the Array is 1, which is greater than 0; hence for query 4 ans will be 0th index.

Approach

For each query, the simplest method is to traverse the Array. Change input[ind] to 'ele' for all Type 1 queries. For the Type 2 query, search the array input[] through the range [L, R] for the lowest index j that meets the given condition. If no such index can be found, print "-1." Queries to find the min index in a range [L, R]  will cost the time complexity of O(N * Q) where ‘N’ is the size of the input array, and ‘Q’ is total queries since for every query. We are iterating the entire Array to optimize this approach. For this, we can use the concept of segment trees. Segment tree will store the maximum value in a given node in that particular range.Now to find the element which is just greater than equal to ‘ele’ can be done in log(N) since we are iteating on a tree. Below is the detailed algorithm and code for an efficient segment tree approach.

Algorithm

  • Create a Segment Tree with each node representing the maximum value in the node's range. For example, the largest value in any given range [i, j] will be stored in the appropriate node.
  • Set ans as the variable to be initialized.
  • If the current range does not fall within the range [L, R], then scan the left subtree for type 2 queries.
  • If the maximum exceeds 'ele' in the left subtree and the current range is within the range [L, R], go to the mid-point of that range and see if its value is more than 'ele.' If this is the case, proceed to the left side of the tree. Otherwise, go to the right part.
  • If the variable ans exists, set it to the minimum index between the given range.
  • Follow the steps above until the left half of the range is equal to the right half.
  • Print the value of ans as a result after completing the preceding steps.

Code:

// Queries to find the min index in a range [L, R] 
#include <bits/stdc++.h>
using namespace std;

// Stores the nodes of segment tree
int segTree[1000];

// Function to build segment tree
void buildTree(int input[], int index,int start, int end)
{

    // Base Case
    if (start == end)
        segTree[index] = input[start];

    else {

        // Finding the mid value
        int mid = (start + end) / 2;

        // Update for left subtree
        buildTree(input, 2 * index, start, mid);

        // Update for right subtree
        buildTree(input, 2 * index + 1,mid + 1, end);

        // Updating the current index
        segTree[index]= max(segTree[2 * index],segTree[2 * index + 1]);
    }
}

// Function to find the index of the first element greater than at least ele
int minEle(int index, int start, int end,int ql, int qr, int ele)
{

    // If current range goes out of query range
    if (ql > end || qr < start)
        return -1;

    // If current range lies inside of query range
    if (start <= ql && end <= qr) {

        // If Maximum value in this range is less than ele
        if (segTree[index] < ele)
            return -1;

        // Finding index of first value in this range
        while (start != end) {
            int mid = (start + end) / 2;

            // Update the value of the minimum index
            if (segTree[2 * index] >= ele) {
                end = mid;
                index = 2 * index;
            }
            else {
                start = mid + 1;
                index = 2 * index + 1;
            }
        }
        return start;
    }

    // Find mid of the current range
    int mid = (start + end) / 2;

    // Left subtree
    int val = minEle(2 * index, start,mid, ql, qr, ele);

    if (val != -1)
        return val;

    // If it does not lie in left subtree
    return minEle(2 * index + 1, mid + 1,end, ql, qr, ele);
}

// Function to update the segment tree
void updateTree(int index, int start, int end,int newvalue, int position)
{

    // Base case
    if (start == end)
        segTree[index] = newvalue;

    else {

        // Find the mid
        int mid = (start + end) / 2;

        if (position <= mid) {

            // Position to update is on left subtree
            updateTree(2 * index, start, mid ,newvalue, position);
        }
        else {

            // Position to update is on right subtree
            updateTree(2 * index + 1,mid + 1, end,newvalue, position);
        }

        // Update the current index
        segTree[index]= max(segTree[2 * index],segTree[2 * index + 1]);
    }
}

// Queries to find the min index in a range [L, R] 
void solve(int* input, int size)
{

    // Build segment tree
    buildTree(input, 1, 0, size - 1);

    //Running queries on the tree
    // Query1
    // Find index of first value at least 2 in range [0, size-1]
    cout << minEle(1, 0, size - 1,0, size - 1, 2)<<endl;


    // Query 2
    // Update value at index 2 to 5
    input[2] = 5;
    updateTree(1, 0, size - 1, 5, 2);

    // Query 3
    // Find index of first value at least 4 in range [0, size-1]
    cout << minEle(1, 0, size - 1,0, size - 1, 4)<<endl;

    // Query 4
    // Find index of first value at least 0 in range [0, size-1]
    cout << minEle(1, 0, size - 1,0, size - 1, 0)<< endl;
}


int main()
{
    int input[] = { 1,4,3,7,2,6,8 };
    int size = sizeof(input) / sizeof(input[0]);

    // Queries to find the min index in a range [L, R] 
    solve(input, size);

    return 0;
}

 

Output:

1
1
0

 

Time Complexity 

O(Q * log N)

The time complexity for the solution of “Queries to find the min index in a range [L, R] having at least value ele with updates” is O(Q * log(N)), where ‘N’ is the size of the input Array. Since we are creating an extra array to store the elements in the form of a segment tree, iterating in the segment tree will only cost log(N) time, where ‘N’ represents a total number of nodes in the tree. So if we operate for Q queries given in the input, the average time complexity for every query can be estimated as O(Q * log(N)).

Space Complexity 

O(N)

The space complexity for the solution of “Queries to find the min index in a range [L, R] having at least value ele with updates” is  O(N), where ‘N’ is the size of the input Array since we are creating an extra array to store the elements in the form of a segment tree.

FAQs

  1. What are segment trees?
    A Segment Tree is a data structure that can successfully answer range queries over an array while also allowing the Array to be modified.
     
  2. Where are segment trees used?
    When there are several range queries on an array and changes to the same Array's elements, a Segment Tree is employed. A segment tree can solve the problem in less time compared to the brute force approach.
     
  3. Why is the segment tree helping in making the solution efficient?
    If we use a basic array then finding minimum will cost linear time complexity and updating will be done in constant time complexity. A Segment Tree is a data structure that effectively answers range queries over an array while remaining flexible enough to allow the array to be modified. This can involve things like calculating the sum of consecutive array elements or determining the smallest element in a time span using segment tree. We can perform the operations in logarithmic time complexity. Segment tree stores the element in the array but in the form of tree hence iterating on it only cost the logarithmic time complexity.

Key Takeaways

In this blog, we discussed the solution of “Queries to find the min index in a range [L, R] having at least value ele with updates”, the article also focused on the time and space complexity of the solution.

 

If you want to learn more about segment trees and want to practice some quality questions which require you to excel your preparation a notch higher, then you can visit our Guided Path for segment trees on CodeStudio.To be more confident in data structures and algorithms, try out our DS and Algo Course. Until then, All the best for your future endeavors, and Keep Coding.

 

Was this article helpful ?
1 upvote