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

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.

Check out this problem - First And Last Occurrences Of X

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 Coding Ninjas Studio.To be more confident in Data Structure and algorithms, try out our DS and Algo Course. Until then, All the best for your future endeavors, and Keep Coding.