[백준] 2357 최솟값과 최댓값, python

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

 

 

 

 

세그먼트 트리, python

세그먼트 트리, python

 

 

 

특정 구간 (a, b) 사이의 최댓값, 최솟값을 m 번 구하는 문제이다.

파이썬의 min, max는 시간복잡도가 O(n) 이므로 모든 (a, b) 부분배열에서 min, max 함수를 사용하게 되면 O(n²) 이 되어 시간초과가 나게 된다.

 

 

따라서 이 문제는 세그먼트 트리를 이용하여 풀어야 한다.

세그먼트 트리란 완전 이진트리에 구간별로 나누어 그 구간 내에서 최대, 최소, 합, 곱 등을 계산해 놓은 트리이다.

완전 이진트리란 마지막 레벨을 제외한 레벨이 가득 차있고, 마지막레벨은 왼쪽부터 채워져 있는 트리를 말한다. 다시 말해 위쪽 왼쪽부터 차례대로 채워나간 것이다.

 

 

세그먼트 트리를 생성하기 위해서는 배열을 범위를 1 단위로 쪼갠다음 2개씩 붙여나가면서 병합해 나가는 방식을 쓴다.

[6 , 3 , 7, 2, 4 ,1]을 세그먼트 트리로 바꾸는 과정이다.

 

 

 

 

트리는 배열로 구현할 수 있다. 트리의 루트노드를 1번으로 하고 왼쪽 위부터 순서대로 인덱스를 정한다.

이렇게 하게 되면 부모노드가 n 일 때 왼쪽 자식노드는 2*n이 되고, 오른쪽 자식노드는 2*n+1 이 된다.

또한 자식노드를 2로 나눈 몫이 부모노드가 된다.

 

 

트리의 리프노드에는 배열의 각각 요소가 들어가야 한다. 

마지막 레벨 노드의 개수가 2^n개라면 이전 노드의 개수는 1+2+...+2^(n-1)의 합인 2^n -1  이므로 트리를 구현할 배열의 길이를 2^(n) * 2개로 설정하면 된다.

 

 

 

 

 

예시에서는 6 , 3 , 7, 2, 4 ,1 총 6개 이므로 리프노드의 최소 길이는 6 이상이어 하고, 2의 거듭제곱 이어야 한다.

따라서 트리의 마지막 레벨의 노드 개수가 8개여야 하고, 트리를 구현할 배열의 총길이는 2*8인 16이 돼야 한다.

 

 

이제 트리의 마지막 레벨에는 각각 길이가 1인 구간을 배치하고, 레벨을 거꾸로 올라가면서 병합하며 최소, 최댓값을 업데이트한다.

길이가 1인 구간에서의 최대 최소 값은 자기 자신이므로 트리배열의 size+i 번째에  배열의 i번째 값을 넣어주면 된다.

 

 

 

 

레벨을 역순으로 올라가면서 

해당노드의 최솟값 = min(왼쪽 자식노드의 최솟값, 오른쪽 자식노드의 최솟값)

해당노드의 최댓값 = max(왼쪽 자식노드의 최댓값, 오른쪽 자식노드의 최댓값)

을 업데이트해주면 된다.

 

 

4번 노드의 경우 자식노드 8,9번을 병합하여 [0,1]의 구간이 되고 그 구간의 최댓값 최솟값이 된다.

5번 노드의 경우에는 2,7번 노드를 병합하여 [2,3] 구간이 된다.

 

 

 

마찬가지로 2번 노드는 4번과 5번 노드의 구간 [0,1]과 [2,3]을 합친 [0,3] 범위가 되고, 최대 최솟값도 업데이트해준다.

 

 

 

이렇게 하면 세그먼트 트리가 완성된다.

 

 

 

세그먼트 트리가 완성됐다면 이제 (a, b) 구간의 최솟값, 최댓값을 구하려면 이 트리를 어떻게 써야 하는지가 문제이다.

기존에 파이썬 내장함수 min, max를 쓰면 O(n)이 걸리는데 이 트리를 사용하면 O(logn)으로 구할 수 있다.

 

 

부모노드의 구간은 오른쪽 자식노드와 왼쪽 자식노드의 구간을 합친 것이 된다.

노드의 번호가 홀수인 경우, 즉 오른쪽 자식노드일 경우에, 부모노드에서 항상 뒤쪽 범위를 가지게 된다. 

반대로 노드 번호가 짝수인 경우, 왼쪽 자식노드일 경우에는 부모노드에서 앞쪽 범위를 가지게 된다.

 

만약 left가 홀수인 경우에 부모노드는 left의 이전 범위를 포함하게 된다. 따라서 이 경우에는 left의 최대 최솟값을 result의 최대 최솟값에 미리 업데이트를 해준 다음, left에 1을 더해서 짝수번으로 바꿔준다.

right가 짝수인 경우에도 부모노드가 right 이후 범위를 포함하게 되므로 result에 미리 반영해 주고, right에 1을 빼서 홀수번으로 바꿔준다.

이렇게 left는 짝수, right를 홀수로 유지하게 되면, 각각의 부모노드는 항상 left, right 사이 구간만을 가지게 된다.

이 과정을 left > right 까지 반복해주면 된다.  

 

 

 

[1,5]의 최대 최솟값을 구하는 과정이다.

a= 1이고 b= 5이다.

 

 

배열의 1번째 요소는 트리의 size+1번째(9번 노드)이고, 5번째 요소는 트리의 size+5번째(13번 노드)이므로  left =9, right = 13에서 시작하게 된다.

 

 

 

 

 

 

left=9 가 홀수이므로 구하려는 최종 최솟값, 최댓값에 미리 반영을 해주고 left에 1을 더해준다.

현재 최종 최솟값: 3, 최댓값:3이다.

 

 

 

 

 

left=10 짝수이고, right=13 홀수이므로 각각의 부모노드는 (left, right) 안쪽 구간에 들게 된다.

따라서 left=5, right =6으로 업데이트해준다.

 

 

 

 

 

left=5 홀수고, right=6 짝수이다. 따라서 각각 left는 +1, right는 -1을 해주면서 최대 최솟값을 업데이트해준다.

left=6, right=5가 된다.

left> right가 되었으므로 탐색을 중단한다. 

 

 

 

import sys
from heapq import heappush, heappop, heapify
input = sys.stdin.readline

n, m = map(int, input().split())
arr = [int(input()) for _ in range(n)]
query = [map(int, input().split()) for _ in range(m)]

# 세그먼트 트리를 구현할 배열의 길이를 구함
size = 1
while size < n:
    size *= 2

# 구간의 최솟값을 갱신할 트리, 최솟값을 갱신할 트리를 만든다.
min_segtree = [10**16]*(size*2)
max_segtree = [-10**16]*(size*2)

# 리프노드에 배열의 값을 저장
for i in range(n):
    min_segtree[size+i] = arr[i]
    max_segtree[size+i] = arr[i]

# 레벨을 역순으로 올라가며 구간 병합
for i in range(size-1,0,-1):
    min_segtree[i] = min(min_segtree[i*2],min_segtree[i*2+1])
    max_segtree[i] = max(max_segtree[i*2],max_segtree[i*2+1])

def solve(l,r):
    segmin = 10**16
    segmax = -10**16
    while l <= r:
        # 왼쪽 자식노드의 번호가 홀수일때
        if l % 2 == 1:
            # 미리 반영하고 노드번호를 1 올린다.
            segmin = min(segmin,min_segtree[l])
            segmax = max(segmax,max_segtree[l])
            l += 1

        # 오른쪽 자식노드의 번호가 짝수일때
        if r % 2 == 0:
            # 미리 반영하고 노드번호를 1 내린다.
            segmin = min(segmin,min_segtree[r])
            segmax = max(segmax,max_segtree[r])
            r -= 1
        # 각각의 부모노드로 이동
        l = l//2
        r = r//2
    
    print(f'{segmin} {segmax}')

for a,b in query:
    # 리프 노드 번호부터 시작
    solve(size+a-1,size+b-1)