Dynamic Range Minimum Queries

import sys
input = sys.stdin.readline

def solve():
    line = input().split()
    if not line:
        return
    n, q = int(line[0]), int(line[1])
    
    data = list(map(int, input().split()))
    
    p = 1
    while p < n:
        p *= 2
        
    tree = [float('inf')] * (2 * p)
    
    for i in range(n):
        tree[p + i] = data[i]
        
    for i in range(p - 1, 0, -1):
        tree[i] = min(tree[2 * i], tree[2 * i + 1])
        
    for _ in range(q):
        query = input().split()
        if query[0] == '1':
            k = int(query[1]) - 1 + p
            u = int(query[2])
            tree[k] = u
            k //= 2
            while k >= 1:
                tree[k] = min(tree[2 * k], tree[2 * k + 1])
                k //= 2
        else:
            a = int(query[1]) - 1 + p
            b = int(query[2]) - 1 + p
            s = float('inf')
            while a <= b:
                if a % 2 == 1:
                    s = min(s, tree[a])
                    a += 1
                if b % 2 == 0:
                    s = min(s, tree[b])
                    b -= 1
                a //= 2
                b //= 2
            sys.stdout.write(str(s) + '\n')

if __name__ == '__main__':
    solve()

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED