[백준] 10868번 - 최솟값 (파이썬)

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

# 최솟값
import sys
input = sys.stdin.readline
MAX = sys.maxsize

N, M = map(int, input().split())
arr = [0]
for _ in range(N):
    arr.append(int(input()))


def update(i, target):
    while i <= N:
        tree[i] = min(tree[i], target)
        i += (i & -i)


def update2(i, target):
    while 0 < i:
        tree2[i] = min(tree2[i], target)
        i -= (i & -i)


def find(start, end):
    result = MAX

    prev = start
    curr = prev + (prev & -prev)
    while curr <= end:
        result = min(result, tree2[prev])
        prev = curr
        curr = prev + (prev & -prev)
    result = min(result, arr[prev])

    prev = end
    curr = prev - (prev & -prev)
    while curr >= start:
        result = min(result, tree[prev])
        prev = curr
        curr = prev - (prev & -prev)

    return result


tree = [MAX] * (N+1)
tree2 = [MAX] * (N+1)
for i, x in enumerate(arr):
    if i > 0:
        update(i, x)
        update2(i, x)

for _ in range(M):
    start, end = map(int, input().split())
    print(find(start, end))

 

자료구조, 펜윅트리

1. 입력을 받고 트리를 두 가지를 할당해준다.

2. 초기값을 이용해서 펜윅트리를 업데이트해준다.

    - update : 앞에서 뒤로 펜윅트리를 만든다.

    - update2 : 뒤에서 앞으로 펜윅트리를 만든다.

3. 구해야 할 구간을 입력받으면서 해당 구간에서의 최솟값을 찾아서 return (find 함수)

    - tree2는 start부터 end전까지 result = min(result, 해당 인덱스의 tree값) 인덱스를 앞으로 이동

    - 중간의 arr값을 참고해서 한 번 더 비교해준다

    - tree는 end부터 start전까지 result = min(result, 해당 인덱스의 tree값) 인덱스를 뒤로 이동

4. 출력

 

구간합 구하기는 end에서 start-1을 빼서 구할 수 있었다.

그러나 최솟값 구하기는 빼서 구할 수 없어서 난감했다.

트리를 두 가지를 정의를 해서 하나는 앞에서부터 펜윅트리를 만들어주고

다른 하나는 뒤에서부터 펜윅트리를 만들어준다.

그러면 중간에 찾기 힘들었던 최솟값들이 겹치지 않아서 찾을 수 있게 된다.

참고 : https://thinkmath2020.tistory.com/709

[알고리즘] Fenwick Tree(펜윅트리)