[백준 11505번] 구간 곱 구하기 (Python3)

import sys
input = sys.stdin.readline
mod = 1000000007

N,M,K = map(int,input().split())

data = [0]*(N+1)
for i in range(N):
  data[i] = int(input())

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) %mod
  return segtree[x]

makeseg(0,N-1,1)

def editseg(n,c,start,end,x):
  if start == end == n:
    segtree[x] = c
  else:
    mid = (start+end)//2
    if n <= mid:
      segtree[x] = editseg(n,c,start,mid,x*2)*segtree[x*2+1] %mod
    else:
      segtree[x] = segtree[x*2]*editseg(n,c,mid+1,end,x*2+1) %mod  
  return segtree[x]

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

for i in range(M+K):
  a,b,c = map(int,input().split())
  if a == 1:
    data[b-1] = c
    editseg(b-1,c,0,N-1,1)
  else:
    print(sumseg(b-1,c-1,0,N-1,1))

 

구간 합 구하기 문제에서 + 기호만 * 기호로 바꾸고 mod 계산만 해주면 끝!

....인 문제인줄 알았는데 바로 틀렸습니다가 떴다.

 

왜 그런가 했더니 문제는 0이었다. 숫자를 0으로 바꾸는 순간 나누기가 불가능해지기 때문이다.

 

그래서 세그먼트 트리를 수정하는 과정을 조금 손봐주어야 했다. 이전 값과 바꿔줄 값의 차이로 쉽게 구현했던 구간 합 구하기와는 살짝 다르게, 세그먼트 트리를 만드는 함수에서처럼 재귀적으로 구현을 해주어야 한다.

 

그래도 원리적으로 어렵거나 한건 없었다.

 

 

오늘의 교훈) 곱하기, 나누기에서 0을 조심하자