14427 수열과 쿼리 15

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

14427번: 수열과 쿼리 15

 

 

 

 

 

문제 접근

세그먼트 트리를 이용해서 풀었다.

세그먼트 트리는 구간합을 구하는 문제에서 쓰이지만 아래의 leaf노드가 아닌 다른 노드에는 구간합을 적어두는 방식으로 사용한다.

이 문제에선 구간합이 아닌 최소값을 비교해서 더작은 값을 적어두는 방식으로 진행했고 루트노드에 최소값을 적어두는것으로 해결했다.

세그트리는 다양하게 쓰이는듯 하다.

 

세그트리를 어떻게 구현하냐에 차이가 있는데

 

우측방식으로 구현했다.

좌측방식은 쓰는사람을 봤는데... 이해가안된다

 

 

 

 

코드

import sys
import math

input = sys.stdin.readline
"""
1. 
"""

N = int(input())
A = list(map(int, input().split()))
M = int(input())
minVal = min(A)

node = math.ceil(math.log2(N))
tree = [[float('inf'), 0] for i in range(2**(node + 1))]
node = 2**node

for i in range(0, N):
  tree[node + i] = [A[i], i + 1]


def initTree(start, end, index):
  if start == end:
    return tree[index]

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


def updateTree(targetIndex, newValue, start, end, index):
  if targetIndex < start or targetIndex > end:
    return
  if start == end:
    tree[index] = [newValue, targetIndex]
    return

  mid = (start + end) // 2
  updateTree(targetIndex, newValue, start, mid, index * 2)
  updateTree(targetIndex, newValue, mid + 1, end, index * 2 + 1)
  tree[index] = min(tree[index * 2], tree[index * 2 + 1])


initTree(1, node, 1)

for m in range(M):
  val = list(map(int, input().split()))
  if val[0] == 1:
    updateTree(val[1], val[2], 1, node, 1)
  else:
    print(tree[1][1])