Dynamic Range Minimum Queries

# RANGE QUERIES
import sys

def build(node, L, R):
    if L == R:
        tree[node] = arr[L]
        return
    mid = (L + R) // 2

    build(2 * node, L, mid)
    build(2 * node + 1, mid + 1, R)
    tree[node] = min(tree[2*node], tree[2*node+1])

def update(node, L, R, k, u):
    if L == R:
        tree[node] = u
        return
    mid = (L+R) // 2

    if k <= mid:
        update(node*2, L, mid, k, u)
    else:
        update(node*2+1, mid+1, R, k, u)

    tree[node] = min(tree[2*node], tree[2*node+1])

def query(node, L, R, a, b):
    if R < a or L > b:
        return float('inf')
    if a <= L and R <= b:
        return tree[node]
    else:
        mid = (L + R) // 2
        
        return min(query(2*node, L, mid, a, b), query(2*node+1, mid+1, R, a, b))

def main():
    input_data = sys.stdin.read().split()

    global arr, tree
    n = int(input_data[0])
    q = int(input_data[1])

    arr = [0] + [int(x) for x in input_data[2:2 + n]]
    tree = [0] * (4 * n)

    build(1, 1, n)

    idx = 2 + n
    out = []

    for _ in range(q):
        type_q = int(input_data[idx])
        arg1 = int(input_data[idx+1])
        arg2=int(input_data[idx+2])
        idx += 3

        if type_q == 1:
            update(1, 1, n, arg1, arg2)
        else:
            ans = query(1, 1, n, arg1, arg2)
            out.append(str(ans))
    sys.stdout.write('\n'.join(out) + '\n')
if __name__ == '__main__':
    main()

Test 1

Verdict: ACCEPTED

Test 2

Verdict: TIME LIMIT EXCEEDED