Dynamic Range Minimum Queries

class SegmentTree:
    def __init__(self,n,  data):
        self.n = n
        self.size = 1
        while self.size < self.n:
            self.size <<= 1
        self.tree = [float('inf')] * (2 * self.size)
        # Build tree
        for i in range(self.n):
            self.tree[self.size + i] = data[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = min(self.tree[2*i], self.tree[2*i + 1])
    
    def update(self, idx, val):
        idx += self.size
        self.tree[idx] = val
        idx //= 2
        while idx > 0:
            self.tree[idx] = min(self.tree[2*idx], self.tree[2*idx + 1])
            idx //= 2
    
    def query(self, left, right):
        left += self.size
        right += self.size
        res = float('inf')
        while left <= right:
            if left % 2 == 1:
                res = min(res, self.tree[left])
                left += 1
            if right % 2 == 0:
                res = min(res, self.tree[right])
                right -= 1
            left //= 2
            right //= 2
        return res


def rangeQuery(n, q, arr, commands):
    result = []
    tree = SegmentTree(n, arr)
    for command in commands:
        if command[0] == 1:
            tree.update(command[1] - 1, command[2])
            # arr[command[1] - 1] = command[2]
        else:
            start, end = command[1] - 1, command[2] - 1
            # min_num = float('inf')
            # for i in range(start, end + 1):
            #     if arr[i] < min_num:
            #         min_num = arr[i]
            min_num = tree.query(start, end)
            # min_num = findMin(sorted(arr[start:end+1]))
            result.append(min_num)
            # print(min_num)
    return result

def main():
    # n, q = 8, 4
    # arr = [3, 2, 4, 5, 1, 1, 5, 3]
    # commands = [[2, 1, 4], [2, 5, 6], [1, 2, 3], [2, 1, 4]]
    # result = rangeQuery(n, q, arr, commands)
    # print(*result, sep='\n')


    n, q = map(int, input().split())
    arr = list(map(int, input().split()))
    commands = [list(map(int, input().split())) for _ in range(q)]
    result = rangeQuery(n, q, arr, commands)
    print(*result, sep='\n')



if __name__ == "__main__":
    main()

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED