Dynamic Range Minimum Queries

import sys 

input = sys.stdin.read().split()

n = int(input[0])
q = int(input[1])


def build() :
    tree = [float('inf')] * (2*n)
    for i in range(n):
        tree[n+i] = int(input[2+i])
    for i in range(n-1,0,-1):
        tree[i] = min(tree[2*i], tree[(2*i)+1])
    return tree
    

def update(tree, idx, value):
    p = idx +n
    tree[p] = value
    while p > 1:
        p = p//2 
        tree[p] = min(tree[2*p], tree[2*p+1])
    return tree

def query(tree, start, end): 
    l = start +n
    r = end +n
    res = float('inf')
    while l <= r: 
        if l%2 ==1 :
            if tree[l] < res : 
                res = tree[l]
            l = l+1
        if r%2 ==0: 
            if tree[r] < res : 
                res = tree[r]
            r = r-1
        l = l//2
        r = r//2
    return res

tree = build()
i = n+2 
for _ in range(q): 
    if int(input[i]) == 1 :
        tree = update(tree, int(input[i+1])-1, int(input[i+2]))
    else : 
        print(query(tree, int(input[i+1])-1, int(input[i+2])-1))
    i = i+3



# class SegmentTree : 
#     def __init__(self, arr):
#         self.arr = arr 
#         self.tree = [None] *(4*len(arr))
#         self.build(0,0,len(arr)-1)

#     def build(self,node,start,end):
#         if end == start : 
#             self.tree[node] = self.arr[start]
#         else : 
#             mid = (start+end)//2
#             self.build(2*node +1, start, mid)
#             self.build(2*node +2, mid+1, end)
#             self.tree[node] = min(self.tree[2*node +1], self.tree[2*node +2])

#     def update(self, node ,start, end, idx ,value):
#         if start == end : 
#             self.arr[idx] = value
#             self.tree[node] = value
#         else : 
#             mid = (start + end)//2
#             if start <= idx <= mid : 
#                 self.update(2*node+1, start, mid, idx ,value)
#             else : 
#                 self.update(2*node +2, mid +1, end,     idx, value)
#             self.tree[node] = min(self.tree[2*node +1], self.tree[2*node +2])


#     def query (self, node, start, end, left, rigth) : 
#         if rigth < start or left > end : 
#             return float('inf')
#         if left <= start and rigth >= end : 
#             return self.tree[node]
#         mid = (start+end)//2
#         return min(self.query(2*node +1,start, mid, left, rigth), self.query(2*node +2, mid +1, end, left, rigth))

# tree = SegmentTree(array)
# i = n+2

# for _ in range(q) : 
#     if data[i] == 1 :
#         tree.update(0,0,n-1,data[i+1]-1, data[i+2])
#     else : 
#         print(tree.query(0,0,n-1,data[i+1]-1,data[i+2]-1))
#     i = i+3

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED