Dynamic Range Minimum Queries

import math

def build_tree(i):
    global x, tree, k, n
    if i >= k + n:
        return math.inf
    if i >= k:
        tree[i] = x[i - k]
        return tree[i]
    tree[i] = min(build_tree(2 * i), build_tree(2 * i + 1))
    return tree[i]

def update(i, u):
    global tree, k
    tree[i] = u
    while i > 1:
        i //= 2
        tree[i] = min(tree[2 * i], tree[2 * i + 1])


def answer(a, b):
    global tree, k
    res = math.inf
    a += k
    b += k
    while a <= b:
        if a % 2 == 1:
            res = min(res, tree[a])
            a += 1
        if b % 2 == 0:
            res = min(res, tree[b])
            b -= 1
        a //= 2
        b //= 2
    return res


n, q = map(int, input().split())
x = list(map(int, input().split()))

k = 2 ** math.ceil(math.log(n, 2))
tree = [math.inf] * (2 * k)

build_tree(1)


for i in range(q):
    a, j, u = map(int, input().split())
    if a == 1:
        update(j - 1 + k, u)
    else:
        print(answer(j - 1, u - 1))

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED