[백준 14438번] 수열과 쿼리 17 (Python3)

import sys
input = sys.stdin.readline

N = int(input())
data = [*map(int,input().split())]

segtree = {}
def makeseg(start,end,x):
  if start == end:
    segtree[x] = data[start]
  else:
    mid = (start+end)//2
    segtree[x] = min(makeseg(start,mid,x*2),makeseg(mid+1,end,x*2+1))
  return segtree[x]

def updateseg(i,v,start,end,x):
  if start == end:
    segtree[x] = v
  else:
    mid = (start+end)//2
    if i <= mid:
      segtree[x] = min(updateseg(i,v,start,mid,x*2),segtree[x*2+1])
    else:
      segtree[x] = min(segtree[x*2],updateseg(i,v,mid+1,end,x*2+1))
  return segtree[x]

def printseg(i,j,start,end,x):
  if i == start and j == end:
    return segtree[x]
  mid = (start+end)//2
  if j <= mid:
    return printseg(i,j,start,mid,x*2)
  if i > mid:
    return printseg(i,j,mid+1,end,x*2+1)
  return min(printseg(i,mid,start,mid,x*2),printseg(mid+1,j,mid+1,end,x*2+1))

makeseg(0,N-1,1)
M = int(input())
for _ in range(M):
  q,i,j = map(int,input().split())
  if q == 1:
    updateseg(i-1,j,0,N-1,1)
  else:
    print(printseg(i-1,j-1,0,N-1,1))

 

수열과 쿼리 16과 풀이가 거의 완전히 똑같고, 오히려 인덱스가 아니라 값을 출력해서 더 간단하다.

세그먼트 트리의 전형적인 문제이다.

 

 

오늘의 교훈) 세그먼트 트리를 잘 활용하자