c++ - Range Minimum Query with space optimised segment tree

Question

I'm trying to work on a problem statement that states: Given an array of integers and a range of indices l and r, find the index that stores the minimum element in that range. In case of multiple minimum values, return the one corresponding to the leftmost index.

This is a standard RMQ problem, that can be solved using a variety of data. structures like Fenwick tree, square-root decomposition, segment tree etc. I know, it's straight forward to implement a recursive approach for segment tree. However, that approach requires the tree to have 4N number of nodes (where N is the number of elements in the original array). I recently came across a space optimised way to build a segment tree, with just 2N nodes. However, the utility functions I've implemented are giving wrong output, would appreciate if someone can point what I've missed.

Below is the code snippet:

void build_tree(vector<int>& nums) {
    // create a segment tree
    vector<int> tree(nums.size()*2);

    for (int i = nums.size(); i < tree.size(); ++i) {
        tree[i] = i-n; // For leaves, just store their index
    }

    // Fill the parent nodes
    for (int i = n-1; i >=0; --i) {
        int left = tree[i*2], right = tree[i*2+1];
            
        if (nums[left] <= nums[right]) {
            tree[i] = left;
        } else {
            tree[i] = right;
        }
    }
}


int query_min_index_in_range(vector<int>& tree, vector<int>& nums, int l, int r) {
        
   l += tree.size()/2, r += tree.size()/2; // Start from the leaves
   int ans = nums[tree[l]] <= nums[tree[r]]? tree[l]:tree[r];
   while (l<=r) {
       // Update the minimum so far
       if (nums[tree[r]] <= nums[ans]) {
           ans = tree[r];
        }
        if (nums[tree[l]] <= nums[ans]) {
            ans = tree[l];
        }
            
        if (l%2 == 1) l++; // If leftmost range
        if (r%2 == 0) r--; // If rightmost range
        l/=2, r/=2; // Move to parent
    }

    return ans;
}
    

question from:https://stackoverflow.com/questions/65832545/range-minimum-query-with-space-optimised-segment-tree

Answer 1

Waitting for answers