[백준 1275번] 커피숍2 (Python3)

import sys
input = sys.stdin.readline

N,Q = map(int,input().split())

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] = makeseg(start,mid,x*2)+makeseg(mid+1,end,x*2+1)
  return segtree[x]

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

def sumseg(a,b,start,end,x):
  if a == start and b == end:
    return segtree[x]
  mid = (start+end)//2
  if b <= mid:
    return sumseg(a,b,start,mid,x*2)
  if a > mid:
    return sumseg(a,b,mid+1,end,x*2+1)
  return sumseg(a,mid,start,mid,x*2)+sumseg(mid+1,b,mid+1,end,x*2+1)

makeseg(0,N-1,1)

for i in range(Q):
  a,b,n,v = map(int,input().split())
  a -= 1
  b -= 1
  n -= 1
  print(sumseg(min(a,b),max(a,b),0,N-1,1))

  dif = v-data[n]
  data[n] = v
  updateseg(n,dif,0,N-1,1)

 

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

다른 세그먼트 트리 문제랑 다를게 거의 없지만 약간의 함정이 숨어있었으니, a~b 까지의 범위의 합을 입력하라는 명령에서 a가 b보다 더 큰 경우가 존재했다.

이걸 고려 안하고 냈더니 recursion error가 났다가 메모리초과가 났다가 했다...

 

 

오늘의 교훈) 범위 입력에 함정이 있을 수 있다.