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;
}