[백준 2357] 최솟값과 최댓값 - 세그먼트 트리

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

2357번: 최솟값과 최댓값

문제

N(1 ≤ N ≤ 100,000) 개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000) 개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자.

여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최소, 최댓값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000 이하의 값을 갖는다.

 

 

 

---

이 문제를 풀기 위해 처음으로 세그먼트 트리 자료구조에 대해 공부하게 되었다. 공부한 것에 대한 포스팅을 정리했다.

 

https://yejin72.tistory.com/117

세그먼트 트리(Segment Tree) 자료구조

 

 

세그먼트 트리에 대한 이해와 더불어, 이 문제는 그것을 활용하여 a~b 구간 내의 최솟값과 최댓값을 구해야 한다.

기존의 누적합 결과물을 담는 트리 하나로는 요구 결과물을 구할 수 없다고 판단되어, 어떠한 누간 내의 최솟값과 최댓값을 담는 minV와 maxV라는 배열을 따로 선언하여 이용했다.

 

각각 구하고자 하는 목적대로 초기화를 진행한 후, 구간 a~b 사이의 최솟값과 최댓값을 구하라는 요구사항이 들어올 때마다 함수를 통해 구간 내 최솟값과 최댓값을 각각 구한 후 출력하였다.

 

 

<< 전체 코드 >>

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
arr = [int(input()) for _ in range(n)]
minV = [int(1e9) for _ in range(n*4)]
maxV = [0 for _ in range(n*4)]


def init_minV(start, end, idx):
    if start == end:
        minV[idx] = min(minV[idx], arr[start])
        return minV[idx]

    mid = (start + end) // 2
    minV[idx] = min(init_minV(start, mid, idx*2), init_minV(mid+1, end, idx*2+1))
    return minV[idx]


def init_maxV(start, end, idx):
    if start == end:
        maxV[idx] = max(maxV[idx], arr[start])
        return maxV[idx]

    mid = (start + end) // 2
    maxV[idx] = max(init_maxV(start, mid, idx*2), init_maxV(mid+1, end, idx*2+1))
    return maxV[idx]


init_minV(0, n-1, 1)
init_maxV(0, n-1, 1)


def interval_minV(start, end, idx, left, right):
    if end < left or right < start:
        return int(1e9)
    if left <= start and end <= right:
        return minV[idx]

    mid = (start + end) // 2
    return min(interval_minV(start, mid, idx*2, left, right), interval_minV(mid+1, end, idx*2+1, left, right))


def interval_maxV(start, end, idx, left, right):
    if end < left or right < start:
        return 0
    if left <= start and end <= right:
        return maxV[idx]

    mid = (start + end) // 2
    return max(interval_maxV(start, mid, idx*2, left, right), interval_maxV(mid+1, end, idx*2+1, left, right))


for _ in range(m):
    a, b = map(int, input().split())
    print(interval_minV(0, n-1, 1, a-1, b-1), interval_maxV(0, n-1, 1, a-1, b-1))