백준 2357 - 최솟값과 최댓값 (Python)

세그먼트 트리를 이용해 최솟값과 최댓값을 구하는 문제입니다.

전체코드

import math
import sys

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

def init(idx, start, end):
    if start == end:
        seg[idx] = (arr[start], arr[start])
        return seg[idx]

    mid = (start + end) // 2
    left = init(idx * 2, start, mid)
    right = init(idx * 2 + 1, mid + 1, end)
 
    seg[idx] = (min(left[0], right[0]), max(left[1], right[1]))

    return seg[idx]

def find(idx, start, end):
    if range2 < start or range1 > end:
        return (10 ** 9 + 1, 0)

    if range1 <= start and end <= range2:
        return seg[idx]

    mid = (start + end) // 2
    left =  find(idx * 2, start, mid)
    right = find(idx * 2 + 1, mid + 1, end)
    
    return (min(left[0], right[0]), max(left[1], right[1]))

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

h = math.ceil(math.log2(n)) + 1
nodeNum = 1 << h
seg = [0 for _ in range(nodeNum)]
init(1, 0, n - 1)

for _ in range(m):
    range1, range2 = map(int, input().split())
    range1, range2 = range1 - 1, range2 - 1
    answer = find(1, 0, n - 1)
    print(answer[0], answer[1])