This implements the code suggested by David Eisenstat (https://stackoverflow.com/a/31107004/1028772) for Range minimum query with implicit Segment tree

RangeIndexMinimumQuery.py

class RangeIndexMinimumQuery:
    def __init__(self, nums):
        self.nums = nums
        self.n = len(nums)
        self.tree = [-1] * (2 * self.n)

        for i in range(len(nums)):
            index = self.n + i
            while index > 0:
                if self.tree[index] < 0 or nums[i] < nums[self.tree[index]]:
                    self.tree[index] = i
                index //= 2

    def min(self, l, r):
        l += self.n
        r += self.n
        ret = self.tree[l]
        while l < r:
            li = self.tree[l]
            ri = self.tree[r-1]
            if self.nums[li] < self.nums[ret] or self.nums[li] == self.nums[ret] and li < ret:
                ret = li
            if self.nums[ri] < self.nums[ret] or self.nums[ri] == self.nums[ret] and ri < ret:
                ret = ri
            l = (l + 1) // 2  # If l is odd, turn to check with right neighbour's parent
            r //= 2  # Make the border next to the left neighbor's parent
        return ret, self.nums[ret]

RangeMinimumQuery.py

class RangeMinimumQuery:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [INF] * (2 * self.n)

        for i in range(len(nums)):
            self.add(self.n + i, nums[i])

    def add(self, index, value):
        while index > 0:
            self.tree[index] = min(self.tree[index], value)
            index //= 2

    def min(self, l, r):
        l += self.n
        r += self.n
        ret = INF
        while l < r:
            ret = min(ret, self.tree[l], self.tree[r - 1])
            l = (l + 1) // 2  # If l is odd, turn to check with right neighbour's parent
            r //= 2  # Make the border next to the left neighbor's parent
        return ret