Dynamic Range Minimum Queries

import sys
input = sys.stdin.readline

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.size = 1
        while self.size < self.n:
            self.size *= 2
        self.tree = [10**18] * (2 * self.size)
        for i in range(self.n):
            self.tree[self.size + i] = arr[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):
        pos = self.size + idx
        self.tree[pos] = val
        pos //= 2
        while pos:
            self.tree[pos] = min(self.tree[2*pos], self.tree[2*pos+1])
            pos //= 2

    def query(self, l, r):
        l += self.size
        r += self.size
        res = 10**18
        while l <= r:
            if l % 2 == 1:
                res = min(res, self.tree[l])
                l += 1
            if r % 2 == 0:
                res = min(res, self.tree[r])
                r -= 1
            l //= 2
            r //= 2
        return res


n, q = map(int, input().split())
arr = list(map(int, input().split()))
st = SegmentTree(arr)

for _ in range(q):
    t, a, b = map(int, input().split())
    if t == 1:
        st.update(a-1, b)
    else:
        print(st.query(a-1, b-1))

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED