백준 14438 : 수열과 쿼리 17 (Python)

본문 링크

import sys
input=sys.stdin.readline

def init(node , start , end):

    if start==end:
        tree[node]=L[start]
        return

    init(node*2 , start  , (start+end)//2)
    init(node*2+1 , (start+end)//2+1 , end)

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

def update(node , start, end , index , value):

    if index<start or index>end:
        return

    if start==end:
        tree[node]=value
        return

    update(node*2 , start , (start+end)//2 , index , value)
    update(node*2+1 , (start+end)//2+1 , end , index , value)

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

def query(node , start  ,end , left , right):

    if left>end or right<start:
        return int(1e9)

    if left<=start and right>=end: #포함하고있다면

        return tree[node]

    return min(query(node*2 , start , (start+end)//2  , left , right) , query(node*2+1,  (start+end)//2+1 , end , left , right))

N=int(input())
L=list(map(int,input().split()))
tree=[0]*(4*N)

init(1,0,N-1)
for i in range(int(input())):

    Q,A,B=map(int,input().split())

    if Q==1:
        update(1 , 0 , N-1 , A-1 , B)
    else:
        print( query(1 , 0 , N-1 ,  A-1, B-1) )

📌 어떻게 접근할 것인가?

세그먼트 트리를 사용하여 풀었습니다.

문제에서 주어지는 대로 update 함수는 값을 변경하도록 만들었고
query 는 찾고자 하는 값이 최소값이므로 return 값을 최소값으로 반환하였습니다.

$0$ 번째 인덱스 부터 시작하였기 때문에 변수를 인덱스로 사용할 경우 -1 를 추가하였습니다.