백준/ Gold 1 문제 , 백준 파이썬 14438 , 수열과 쿼리 17 [세그먼트 트리]

백준/ Gold 1 문제 , 백준 파이썬 14438 , 수열과 쿼리 17 [세그먼트 트리]

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>

 

문제 출처

 

https://www.acmicpc.net/problem/14438

14438번: 수열과 쿼리 17

 

 

 

 

풀이

 

 

1. 세그먼트 트리 생성 함수

 

이번에는 연산을 하는 것이 아닌 가장 작은 값을 찾는 것이다.

 

init 함수를 재귀적으로 양쪽으로 두번 호출해나가면서 트리에 각 자식노드들중 작은 값을 부여한다.

 

 

2. 특정 노드 변경 함수

 

특정 부분의 노드가 변경 되면 그의 자식, 부모 노드들 또한 값이 변경 될 수 있으므로 min을 각 자식노드들과 비교하여 tree를 재할당한다.

 

 

 

3. 가장 작은 값을 찾는 함수

 

min 을 사용해서 제대로 된 값을 갖게 하기 위해 sys.maxsize를 사용한다.

 

특정 구역의 left~right 를 입력받아 그 구간에서의 최솟값을 리턴시킨다.

 

 

 

 

4. 입력 받기 및 각 함수 호출

 

arr 배열도 변경하는 것을 잊지말자.

 

 

 

정답

 

 

import sys
input=sys.stdin.readline

def init(start,end,index):
    if start==end:
        tree[index]=arr[start]
    else:
        mid=(start+end)//2
        init(start,mid,index*2)
        init(mid+1,end,index*2+1)
        tree[index]=min(tree[index*2],tree[index*2+1])
    return tree[index]

def update(start,end,index,what,value):
    if start>what or end<what:
        return
    if start==end:
        tree[index]=value
        return
    mid=(start+end)//2
    update(start,mid,index*2,what,value)
    update(mid+1,end,index*2+1,what,value)
    tree[index]=min(tree[index*2],tree[index*2+1])
    
def find_min(start,end,index,left,right):
    if left>end or right<start:
        return sys.maxsize
    if left<=start and right>=end:
        return tree[index]
    mid=(start+end)//2
    return min(find_min(start,mid,index*2,left,right),find_min(mid+1,end,index*2+1,left,right))

N=int(input())
arr=list(map(int,input().rstrip().split()))

tree=[0]*(N*4)
init(0,N-1,1)

for _ in range(int(input())):
    a,b,c,=map(int,input().split())
    if a==1:
        update(0,N-1,1,b-1,c)
        arr[b-1]=c
    elif a==2:
        print(find_min(0,N-1,1,b-1,c-1))