[Segment Tree] 백준 - 최솟값과 최댓값 2357번

최솟값과 최댓값 2357번

👏 key point

N(1 ≤ N ≤ 100,000)개의 정수들을 구간별로 지정하여 선형적으로 최대 최소를 구하려면 상당한 시간이 소요된다. (시간복잡도 O(n^2)). 따라서 세그먼트 트리를 통해 풀 경우 O(logn)으로 구간을 탐색하기 때문에 훨씬 빠르게 최대 최소를 찾을 수 있다.

🎂 코드

import sys
    input = sys.stdin.readline

    n,m = map(int, input().split())

    lst = []

    tree = [0] * (n*4)

    for _ in range(n):
        lst.append(int(input()))

    #최소 최대 구간 트리 생성
    def min_max_tree(start, end, node):
        if start == end:
            tree[node] = [lst[start],lst[start]]
            return tree[node]

        mid = (start + end) // 2

        l = min_max_tree(start, mid, node*2)
        r = min_max_tree(mid+1, end, node*2+1)

        tree[node] = [min(l[0],r[0]), max(l[1],r[1])]

        return tree[node]

    #구간 별 최대 최소 구하는 함수
    def interval(start, end, node, left, right):
    
        if left > end or right < start:
            return [1000000001,0]

        if left <= start and end <= right:
            return tree[node]

        mid = (start + end) // 2
        
        l = interval(start, mid, node*2, left, right)
        r = interval(mid + 1, end, node*2+1, left, right)         
        
        return [min(l[0],r[0]), max(l[1],r[1])]

    min_max_tree(0,n-1,1)

    for _ in range(m):
        a,b = map(int, input().split())
        result = interval(0,n-1,1,a-1,b-1)
        print(result[0],result[1])