<구간 곱 구하기>

난이도 : 골드 1

난 이해를 못했다. 그냥 게시판 짜집기했다.

왜 1000000007지? MOD 범위를 벗어난 값에 대해 출력된 나머지는 틀린값 아닌가?

1. 백준 문제
   11505

2. 코드 알고리즘

• 세그먼트 트리
  세그먼트 트리

• 11505
  

3. 코드

#11505
#https://www.acmicpc.net/problem/11505

import sys
input = sys.stdin.readline
import math

N, M, K = map(int, input().split()) #5 2 2
tree_size = math.ceil(math.log2(N)) #k = 3
tree_hight = tree_size+1
left_NodeStart = 2**(tree_size)
tree = [1]*(left_NodeStart*2) #left_NodeStart*2가 트리 리스트 크기
max = 1000000007

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

def toTreeIndex(index):
    while index > 0:
        pivot = index%2
        tree[index//2] *= (tree[index]%max) * (tree[index+(-1)**(pivot)] %max) %max
        index -= 2

toTreeIndex(left_NodeStart*2-1)

def changeNode(start_index, change):
    tree[start_index] = change
    while start_index>0:
        pivot = start_index%2
        tree[start_index//2] = (tree[start_index]%max) * (tree[start_index+(-1)**(pivot)] %max) %max
        #홀수면 pivot=1, 짝수면 pivot=0
        start_index = start_index//2

def partialProduct(start_index, end_index):
    global pProduct
    while start_index <= end_index:
        if (start_index%2) == 1:
            pProduct *= tree[start_index]
            start_index+=1
        if (end_index%2) == 0:
            pProduct *= tree[end_index]
            end_index-=1
        start_index = start_index//2
        end_index = end_index//2
    return (pProduct%max)


for i in range(M+K):
    a, b, c = map(int, input().split())
    if a == 1:
        start_index = b+left_NodeStart-1 #left_NodeStart = 2**k
        #데이터 순서를 세그먼트트리 리스트 인덱스로 바꿔주기
        changeNode(start_index, c)
    elif a == 2:
        pProduct = 1
        start_index = b + left_NodeStart - 1
        end_index =  c + left_NodeStart - 1
        print(partialProduct(start_index, end_index))

4. 코드 후기

• 시간 초과
  tree[부모노드] = tree[왼쪽노드] * tree[오른쪽노드]로 계산하면 시간초과가 나기 때문에 MOD 연산 로직을 사용해야 된다.
  대신 이때 %시행하는 MOD 값을 크게 잡아야 된다

근데 왜 1000000007이냐고!!!!!
계속 틀려서 그냥 게시판 다른 코드의 MOD 값 베꼈는데
(MOD 1000001 -> 1000000007로 수정했더니 되더라)
근데 왜 되는건지...