C - How to return index of minimum element in range query?-CodePudding

I am trying to implement range queries on a segment tree (a binary tree). I am trying to modify the query function so that it can return the index of the minimum value over a range instead of the actual minimum value (which it is currently returning).

Tree, update and query functions:

int length; // This is the length of the array I am querying
int tree[1000000]; // This is a binary tree

// You call update at the start with the index you want to change and the value you want to change it to
void update(int index, int value, int position = 1, int currentL = 0, int currentR = length-1) {
    if (currentL == currentR) {
        tree[position] = value;
        return;
    }
    int mid = (currentL currentR)/2;
    if (index <= mid) {
        update(index, value, position*2, currentL, mid);
    } else {
        update(index, value, position*2 1, mid 1, currentR);
    }
    tree[c] = min(tree[position*2], tree[position*2 1]);
}

// You call query with the range you want to query over
int query(int qL, int qR, int c = 1, int cL = 0, int cR = length-1) {
    if (qL <= cL && cR <= qR) {
        return tree[c];
    }
    int mid = (cL cR)/2;
    int ans = 10005;
    if (qL <= mid) {
        ans = min(ans, query(qL, qR, 2*c, cL, mid));
    }
    if (qR > mid) {
        ans = min(ans, query(qL, qR, 2*c 1, mid 1, cR));
    }
    return ans;
}

Is there a way to change the query function so that it returns not just the minimum value of a range in the array, but also the index of that value?

CodePudding user response：

You can save index together with the value in segment tree by using, e.g., std::pair<int, int> as tree node. If at the leafs we define the pair to be { value, index } for corresponding array element, other nodes should contain pairs { minimal value, its leftmost index } for corresponding range. Since comparison operators for std::pair are defined as lexicographical over constituents, using std::min (which is based on operator< if comparator is not explicitly provided) the same way as in your code will lead to choosing, for each node/range, minimal of child-nodes/subrange minimums together with its index (smaller one will be chosen if minimums are equal, because second pair element is used for comparison then), so it will produce desired accumulation of ranges. Code:

std::pair<int, int> tree[1000000];

void update(int index, int value, int position = 1, int currentL = 0, int currentR = length-1) {
    if (currentL == currentR) {
        tree[position] = { value, index };
        return;
    }
    int mid = (currentL currentR)/2;
    if (index <= mid) {
        update(index, value, position*2, currentL, mid);
    } else {
        update(index, value, position*2 1, mid 1, currentR);
    }
    tree[c] = min(tree[position*2], tree[position*2 1]);
}

std::pair<int, int> query(int qL, int qR, int c = 1, int cL = 0, int cR = length-1) {
    if (qL <= cL && cR <= qR) {
        return tree[c];
    }
    int mid = (cL cR)/2;
    std::pair<int, int> ans = { std::numeric_limits<int>::max(), std::numeric_limits<int>::max() };
    if (qL <= mid) {
        ans = min(ans, query(qL, qR, 2*c, cL, mid));
    }
    if (qR > mid) {
        ans = min(ans, query(qL, qR, 2*c 1, mid 1, cR));
    }
    return ans;
}

Of course, to make code more readable custom struct with proper data member names may be used, but then you have to define comparison operator(s) yourself (or pass comparators to std::min). Also note that that I used std::numerical_limits (doc) for initial ans value since it's more generic and idiomatic.

CodePudding user response：

There are several ways you can return the index of the minimum element in a range query. One way is to use a data structure such as a segment tree, which allows you to perform range queries and update operations in logarithmic time. To find the minimum element in a range, you can perform a range query on the segment tree, and then iterate through the returned elements to find the minimum element and its index.

Here is an example of how you could implement this in Python using a segment tree:

    from math import log2

class SegmentTree:
    def __init__(self, arr):
        self.arr = arr
        self.n = len(arr)
        self.seg_tree = [0] * (4 * self.n)
        self.build(1, 0, self.n - 1)

    def build(self, node, start, end):
        if start == end:
            self.seg_tree[node] = (self.arr[start], start)
        else:
            mid = (start   end) // 2
            self.build(2 * node, start, mid)
            self.build(2 * node   1, mid   1, end)
            self.seg_tree[node] = min(self.seg_tree[2 * node], self.seg_tree[2 * node   1], key=lambda x: x[0])

    def query(self, node, start, end, l, r):
        if r < start or end < l:
            return float("inf"), -1
        if l <= start and end <= r:
            return self.seg_tree[node]
        mid = (start   end) // 2
        left = self.query(2 * node, start, mid, l, r)
        right = self.query(2 * node   1, mid   1, end, l, r)
        return min(left, right, key=lambda x: x[0])

# Example usage
arr = [3, 2, 1, 4, 5]
seg_tree = SegmentTree(arr)

# Find the minimum element and its index in the range [1, 3] (indexes are 0-based)
min_element, min_index = seg_tree.query(1, 0, len(arr) - 1, 1, 3)
print(f"The minimum element in the range is {min_element} at index {min_index}")
# Output: The minimum element in the range is 1 at index 2

Another option is to use a data structure such as a Fenwick tree or a Binary Indexed Tree (BIT). These data structures can also be used to perform range queries and update operations in logarithmic time. To find the minimum element in a range, you can perform a range query on the Fenwick tree or BIT, and then iterate through the returned elements to find the minimum element and its index.

Here is an example of how you could implement this in Python using a Fenwick tree:

class FenwickTree:
def __init__(self, n):
    self.n = n
    self.tree = [0] * (n   1)

def update(self, i, delta):
    i  = 1
    while i <= self.n:
        self.tree[i]