[BOJ] 11505 - 구간 곱 구하기 (Python)

 

 

아이디어

 

세그먼트 트리로 구간 곱을 저장해두고 변경이나 계산이 필요한 구간에 대해 빠르게 처리한다.

 

 

풀이

 

2042번 구간 합 구하기 문제와 유사한 문제로, 합이 아닌 곱을 저장하면 된다.

 

구간 곱을 계산하기 위해 N보다 크면서 가장 작은 2의 거듭제곱의 두 배 크기로 1로 채워진 리스트 tree를 만든다.

트리의 리프 노드들에는 순서대로 N개의 수를 입력 받고, for문에서 각 부모 노드에 두 자식 노드의 곱을 저장한다.

이후 for문에서는 a가 1이라면 해당 트리 리프 노드의 수를 변경한 후 함수 update를, a가 2라면 함수 multiply를 호출한다.

 

함수 update에서는 리프 노드의 부모 노드부터 루트 노드까지 다시 계산하고, 재귀 호출로 루트 노드를 벗어나면 종료한다.

 

함수 multiply에서는 리프 노드에서부터 차례로 해당 노드의 부모 노드로 올라가며 구간 곱을 결과값 res에 곱해 나간다.

부모 노드의 값은 두 자식 노드 값의 곱이므로 s%2 == 1 또는 e%2 == 0처럼 형제 노드 중 한 노드만 포함되어 있는 경우

해당 노드 값을 res에 곱한 후 인덱스를 이동하여 부모 노드의 값을 곱하지 않도록 한다.

 

구간 합에서는 트리 초기값을 덧셈의 항등원인 0으로 채웠다면, 구간 곱은 곱셈의 항등원인 1로 채운다.

또 중간 계산 과정에서도 1,000,000,007로 나눈 나머지를 저장한다.

 

import sys

input = sys.stdin.readline

def update(idx):
    while idx > 0:
        tree[idx] = tree[idx*2]*tree[idx*2+1]%1000000007
        idx //= 2

def multiply(s, e):
    res = 1
    while s <= e:
        if s%2:
            res *= tree[s]
            s += 1
        if e%2 == 0:
            res *= tree[e]
            e -= 1
        s, e = s//2, e//2
        res %= 1000000007
    return res

N, M, K = map(int, input().split())
n = 1
while n < N:
    n *= 2
tree = [1]*(n*2)
tree[n:n+N] = [int(input()) for _ in range(N)]
for i in range(n-1, 0, -1):
    tree[i] = tree[i*2]*tree[i*2+1]%1000000007
for _ in range(M+K):
    a, b, c = map(int, input().split())
    if a == 1:
        tree[n+b-1] = c
        update((n+b-1)//2)
    else:
        print(multiply(n+b-1, n+c-1))