Dynamic Range Minimum Queries

import sys
input = sys.stdin.readline

def build(node, l, r):
    if l == r:
        seg[node] = arr[l]
    else:
        m = (l + r) // 2
        build(2*node, l, m)
        build(2*node+1, m+1, r)
        seg[node] = min(seg[2*node], seg[2*node+1])

def update(node, l, r, idx, val):
    if l == r:
        seg[node] = val
    else:
        m = (l + r) // 2
        if idx <= m:
            update(2*node, l, m, idx, val)
        else:
            update(2*node+1, m+1, r, idx, val)
        seg[node] = min(seg[2*node], seg[2*node+1])

def query(node, l, r, ql, qr):
    if qr < l or r < ql:
        return 10**18
    if ql <= l and r <= qr:
        return seg[node]
    m = (l + r) // 2
    return min(query(2*node, l, m, ql, qr), query(2*node+1, m+1, r, ql, qr))

n, q = map(int, input().split())
arr = [0] + list(map(int, input().split()))
seg = [0] * (4*n)
build(1, 1, n)

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

Test 1

Verdict: ACCEPTED

Test 2

Verdict: TIME LIMIT EXCEEDED