[Python][백준 14438][세그먼트 트리] 수열과 쿼리 17 - 컴도리돌이

14438번: 수열과 쿼리 17

---

풀이 과정

해당 문제는 세그먼트 트리를 알고 있어야 해결할 수 있습니다.

쿼리의 개수가 십만 개인데 배열의 크기마저 최대가 10^9입니다.

해당 문제를 단순하게 인덱스 사이의 min 값으로 출력하게끔 설정하면

0.1초 만에 시간 초과를 보게 될 것입니다.

😶‍🌫️

 

그렇다면 세그먼트 트리가 무엇인가?

배열의 "연속적인" 구간 합 또는 구간의 min, max 값을 찾을 때 사용하는 알고리즘으로

단순 선형적인 자료구조에서 위에 것을 구하려고 하면 최악의 경우 

모든 배열을 탐색해야 합니다. => O(N)

 

만약 도중에 배열의 값을 변경한다면 

한번 처리할 때마다 O(1)이고 M개를 변경할 경우 O(M)의 시간이 걸립니다.

 

그러면 탐색 및 수정을 할 때 O(N+M) 시간 복잡도가 걸리겠네요 거기다가 쿼리문까지 포함되면 

시간 복잡도는 더 커지겠죠..

 

세그먼트 트리를 쓴다면 O(logN)에 처리할 수 있습니다!!

 

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

 

1-1 노드가 리프 노드인 경우,

리프 노드는 배열의 그 원소를 가져야 하기 때문에 

tree[node] = A[start]를 반환

 

1-2 재귀 함수를 이용해서

왼쪽 자식과 오른쪽 자식 트리에서 min값을

tree[node]에 저장한다.

 

2. 세그먼트 트리 update(수정) 함수 생성

 

2-1 루트 노드가 리프 노드일 경우

입력받은 값으로 업데이트해주고 

반환해준다.

 

2-2 왼쪽 자식과 오른쪽 자식으로 업데이트해준다.

 

2-3 왼쪽과 오른쪽 자식 중의 min 값을 현재 node에 저장한다.

 

3. 세그먼트 트리 findMin(구간 내의 min 값 찾기) 함수 생성

 

3-1 겹치지 않은 범위는 매우 큰 값을 반환해준다.

 

3-2 구해야 하는 범위 left, right가 start, end에 포함될 경우

노드의 자식도 모두 포함되기 때문에 

현재 노드의 값을 반환해준다.

 

3-3 왼쪽 자식과 오른쪽 자식 중의 min값을 반환해준다.

 

 

아마도 세그먼트 트리를 완전히 이해해야지 제가 위에 간단하게 작성한 것이

이해가 될 거예요..

🥲🥲

---

풀이 코드

import sys; input = sys.stdin.readline
mid = lambda a,b  : (a+b)//2
def init(node,start,end) :
  if start == end :
    tree[node] = A[start]
  else :
    init(node * 2, start,mid(start,end))
    init(node * 2 + 1, mid(start,end) + 1, end)
    tree[node] = min(tree[node*2],tree[node * 2 + 1])
def update(node,start,end,index,num) :
  if index < start or index > end : return 
  if start == end : 
    A[start],tree[node] = num,num
    return tree[node]
  update(node * 2 , start,mid(start,end), index,num)
  update(node * 2 + 1 , mid(start,end)+ 1,end, index, num)
  tree[node] = min(tree[node*2],tree[node*2 + 1])
  
def findMin(node,start,end,left,right) :
  if left > end or right < start : return 2e9
  if left <= start and end <= right : return tree[node]
  return min(findMin(node*2,start,mid(start,end),left,right),findMin(node*2 + 1,mid(start,end)+1,end,left,right))
  
n = int(input())
A = [0] + list(map(int,input().split()))
tree = [0] * 270000
init(1,1,n)

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