[백준] 10686번 - 최소값

10868번: 최솟값

해당문제는 세그먼트 트리로 문제를 해결 할 수 있습니다. M개의 쿼리가 주어진다면 Mlog(n)의 시간 복잡도로 문제를 해결 할 수 있습니다.

초기화

• 세그먼트 트리를 초기화를 통하여 세그먼트 트리를 만듭니다.
• 초기화 하는 과정은 재귀로 각각의 Leaf Node까지 방문한뒤 Leaf Node로부터 다시 올라가면서 Node위치에 자기자신의 최소값을 업데이트 합니다.

쿼리

• 구간의 최소값을 검색하는 쿼리로 log(n)의 시간복잡도로 구간 최소값을 구합니다.
• 쿼리를 할때의 조건은 3가지로 나누어 질수 있는데 (start,end) 가 쿼리의 범위이고, (left,right)가 찾는 범위라고 한다면
  1. 범위안에 없는경우 : 해당값은 찾을 수 없음
  2. 범위안에 있는경우 : 바로 tree[node]값을 리턴한다.
  3. 범위가 걸쳐있는경우 : 이분탐색으로 tree[node]값을 가져온다.
• 범위안에 있는경우와 범위에 걸쳐있는경우를 모두 탐색하여 최소값을 찾아낸다. 범위 안에 없는경우는 무시해야함으로, 무한대값을 리턴한다.

import math
import sys
input = sys.stdin.readline
INF = int(1e10)

N, M = map(int, input().split())
arr = [0 for _ in range(N+1)]
treesize = int(pow(2,(math.ceil(math.log2(N)))+1))
tree = [INF for _ in range(treesize)]

def init(node, start, end):
    if start == end: # leaf node
        tree[node] = arr[start]
        return tree[node]

    mid = (start + end) // 2
    tree[node] = min(init(node*2, start, mid), init(node*2+1, mid+1, end))
    return tree[node]

def query(node, start, end, left, right):
    if right < start or left > end: # 범위 이상인경우
        return INF

    if left <= start and right >= end: # 범위 안에 있는경우
        return tree[node]

    # 범위가 걸쳐서 있는경우
    mid = (start + end) // 2
    leftmin = query(node*2, start, mid, left, right)
    rightmin = query(node*2+1, mid+1, end, left, right)
    return min(leftmin, rightmin)

def update(node, start, end, idx, diff):
    if start == end: # leaf node
        tree[node] += diff
        return

    mid = (start + end) // 2
    if start <= idx <= mid:
        return update(node*2, start, mid, idx, diff)
    else:
        return update(node*2+1, mid +1, start, idx, diff)

for i in range(1, N+1):
    arr[i] = int(input())

init(1, 1, N)
for _ in range(M):
    a, b = map(int, input().split())
    print(query(1, 1, N, a, b))