[백준] 11505번 - 구간 곱 구하기

---

문제 분석

이 문제를 풀기에 앞서 다음과 같은 개념이 필요하다.

(A*B) % C == (A%C)*(B%C) % C
위의 개념을 인지하며, 세그 먼트 트리를 이용해 풀면된다.

---

소스 코드

import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
treeHeight = 0
length = N
MOD = 1000000007

while length != 0:
    length //= 2
    treeHeight += 1

treeSize = pow(2, treeHeight + 1)
leftNodeStartIndex = treeSize // 2 - 1
tree = [1] * (treeSize + 1)

for i in range(leftNodeStartIndex + 1, leftNodeStartIndex + N + 1):
    tree[i] = int(input())


def setTree(i):
    while i != 1:
        tree[i//2] = tree[i//2] * tree[i] % MOD
        i -= 1


setTree(treeSize - 1)


def changeVal(index, value):
    tree[index] = value
    while index > 1:
        index = index // 2
        tree[index] = tree[index*2] % MOD * tree[index*2 + 1] % MOD


def getMul(s, e):
    partMul = 1
    while s <= e:
        if s % 2 == 1:
            partMul = partMul * tree[s] % MOD
            s += 1
        if e % 2 == 0:
            partMul = partMul*tree[e] % MOD
            e -= 1
        s = s//2
        e = e//2
    return partMul


for _ in range(M+K):
    question, s, e = map(int, input().split())
    if question == 1:
        changeVal(leftNodeStartIndex+s, e)
    elif question == 2:
        s = s+leftNodeStartIndex
        e = e+leftNodeStartIndex
        print(getMul(s, e))