백준 - 최댓값과 최솟값 2357(세그트리, 골1)

문제풀러가기

구간별 최솟값과 최댓값을 구하는 문제이다. min, max함수는 모두
O(N) 이 걸리기 때문에 사용하지 못했고 세그먼트 트리를 활용해서 문제를 풀어야한다.

세그먼트 트리

특정 구간에 대한 질의를 처리하거나 자료의 업데이트가 빈번할 때 효율적인 자료구조이다.

루트는 전체 구간의 정보를 담고 있다. 왼쪽 자식 노드와 오른쪽 자식 노드는 부모 노드가 표현하는 구간의 왼쪽 절반에 대한 정보, 오른쪽 절반에 대한 정보를 포함한다.

구간을 절반씩 나눠서 정보를 포함하기 때문에 O(logN) 안에 정해진 구간에서 원하는 값을 구할 수 있다.

해당 문제에서는 특정 범위에서의 최댓값과 최솟값을 구하는 문제이다.

세그먼트 트리를 만드는 방법은 Bottom-Up 방식과 Top-Down 방식이 존재한다.
아무래도 재귀를 이용하는 Top-Down 방식보다 Bottom-Up 방식이 좀 더 빠르다.

Top-Down

'''
24 02 22
최솟값과 최댓값
백준 2357
골1
세그트리
'''
import sys, math


def makeSegTree(idx, start, end):
    if start == end:
        segTree[idx] = (number[start], number[start])
        return segTree[idx]

    mid = (start + end) // 2
    left = makeSegTree(idx * 2, start, mid)
    right = makeSegTree(idx * 2 + 1, mid + 1, end)

    segTree[idx] = (min(left[0], right[0]), max(left[1], right[1]))

    return segTree[idx]


def find(idx, start, end, x, y):
    if y < start or x > end:
        return (sys.maxsize, -sys.maxsize)

    if x <= start and end <= y:
        return segTree[idx]

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


N, M = map(int, sys.stdin.readline().strip().split(" "))
number = []
H = math.ceil(math.log2(N)) + 1
segTree = [(sys.maxsize, -sys.maxsize) for _ in range(2 ** H)]

for _ in range(N):
    number.append(int(sys.stdin.readline()))

makeSegTree(1, 0, N - 1)
for _ in range(M):
    a, b = map(int, sys.stdin.readline().split(" "))
    print(*find(1, 0, N - 1, a - 1, b - 1))

Bottom-Up

다른 풀이 참고

import sys
r = lambda: sys.stdin.readline()
input = sys.stdin.readline
N, M = map(int, input().split())
max_tree = [0] * (N*2)
min_tree = [0] * (N*2)

# Build maximum segment tree
def build_max_tree(N):
    for i in range(N-1, 0, -1):
        max_tree[i] = max(max_tree[i*2], max_tree[i*2+1])

# Build minimum segment tree
def build_min_tree(N):
    for i in range(N-1, 0, -1):
        min_tree[i] = min(min_tree[i*2], min_tree[i*2+1])

# Perform range maximum query
def max_query(left, right):
    left += N
    right += N
    max_val = 0
    while left <= right:
        if left % 2 == 1:
            max_val = max(max_val, max_tree[left])
            left += 1
        if right % 2 == 0:
            max_val = max(max_val, max_tree[right])
            right -= 1
        left //= 2
        right //= 2
    return max_val

# Perform range minimum query
def min_query(left, right):
    left += N
    right += N
    min_val = 10000000000
    while left <= right:
        if left % 2 == 1:
            min_val = min(min_val, min_tree[left])
            left += 1
        if right % 2 == 0:
            min_val = min(min_val, min_tree[right])
            right -= 1
        left //= 2
        right //= 2
    return min_val

for i in range(N):
    xxx = int(input())
    max_tree[N+i] = xxx
    min_tree[N+i] = xxx
build_max_tree(N)
build_min_tree(N)

for i in range(M):
    left, right = map(int, input().split())
    x = max_query(left-1, right-1)
    y = min_query(left-1, right-1)
    print(y, x)