백준 14427 수열과 쿼리 15 python

최근에 한 기업의 코테에서 세그먼트 트리관련 문제가 나왔다고 해서 공부해봤다.
아직 아리송한 부분들이 많은데 몇 문제 더 풀어봐야 알 수 있을 거 같다.

📜 문제 바로 가기 : 수열과 쿼리 15

제출코드

파이썬

import sys
input = sys.stdin.readline

def merge(a, b):
    if arr[a] <= arr[b]: # 같다면 인덱스가 작은 쪽 리턴
        return a
    return b

def buildTree(node, start, end):
    if start == end:
        segmentTree[node] = start
        return segmentTree[node]
    
    mid = (start + end) // 2
    left = buildTree(node*2, start, mid)
    right = buildTree(node*2 + 1, mid+1, end)

    segmentTree[node] = merge(left, right)
    return segmentTree[node]

def upDate(targetIdx, newValue, node, start, end):

    if targetIdx < start or targetIdx > end:
        return segmentTree[node]

    if start == end:
        arr[targetIdx] = newValue
        return segmentTree[node]
    
    mid = (start + end) // 2
    left = upDate(targetIdx, newValue, node*2, start, mid)
    right = upDate(targetIdx, newValue, node*2 + 1, mid+1, end)

    segmentTree[node] = merge(left, right)
    return segmentTree[node]


N = int(input())
arr = list(map(int, input().split()))

segmentTree = [-1] * (4 * N)
buildTree(1, 0, N-1)

M = int(input())
for _ in range(M):
    k, *com = map(int, input().split())
    if k == 1:
        upDate(com[0]-1, com[1], 1, 0, N-1)
    else:
        print(segmentTree[1]+1)

---

접근방법

백준의 세그먼트 트리문제로 분류된 것 중 가장 난이도가 낮은 문제였다.

세그먼트 트리의 구현은 아래 유뷰트를 참고하여 공부했다.

https://www.youtube.com/watch?v=075fcq7oCC8
https://www.youtube.com/watch?v=ahFB9eCnI6c