백준 11505 구간 곱 구하기

문제

👀 문제 사이트 : https://www.acmicpc.net/problem/11505

풀이

난이도 : GOLD I

이 문제는 숫자가 저장된 배열에서 최대합, 혹은 최대곱 등을 효율적으로 구할 수 있도록 값을 저장하는 세그먼트 트리 정의를 그대로 나타낸 문제이다.

• 백준 2042 구간 합 구하기 문제 풀이 링크
• 2042 번 문제는 이 문제와 거의 똑같은 문제이며, 구간 합과 구간 곱이라는 부분만 다르다.
• 2042 번 풀이에서 세그먼트 트리 자료구조에 대하여 설명하였다.

✔ 주의할 점

• 이 문제는 input 양이 많으므로 sys.stdin.readline으로 입력받아야 한다.
• 이 문제는 구간 합 구하기 문제와 다르게 구간 곱을 구해야 하므로 값이 크게 증가하기 때문에 문제에 1,000,000,007로 나눈 나머지를 출력하라고 주어져 있다. 따라서 값을 저장할 때 이 부분을 주의하여야 한다.
  

코드

import sys

# 세그먼트 트리 build (1000000007 이하)
def segment_tree_build(node, start, end):
    if start == end:
        tree[node] = numbers[start - 1]
    else:
        mid = (start + end) // 2
        segment_tree_build(node * 2, start, mid)
        segment_tree_build(node * 2 + 1, mid + 1, end)
        tree[node] = (tree[node * 2] * tree[node * 2 + 1]) % 1000000007

# 세그먼트 트리에서 구간 곱 구하기
def segment_tree_rangemul(node, start, end, left, right):
    if start > right or end < left:
        return 1
    if start >= left and end <= right:
        return tree[node]
    
    mid = (start + end) // 2
    p1 = segment_tree_rangemul(node * 2, start, mid, left, right)
    p2 = segment_tree_rangemul(node * 2 + 1, mid + 1, end, left, right)
    return p1 * p2

# 세그먼트 트리에서 업데이트하기
def segment_tree_update(node, start, end, idx, val):
    if start == end:
        numbers[idx - 1] = val
        tree[node] = val
    else:
        mid = (start + end) // 2
        if start <= idx and idx <= mid:
            segment_tree_update(node * 2, start, mid, idx, val)
        else:
            segment_tree_update(node * 2 + 1, mid + 1, end, idx, val)
        tree[node] = (tree[node * 2] * tree[node * 2 + 1]) % 1000000007

input = sys.stdin.readline
n, m, k = map(int, input().split())
numbers = []
tree = [0] * (10 * n)

for _ in range(n):
    numbers.append(int(input()))

segment_tree_build(1, 1, n)
for _ in range(m + k):
    a, b, c = map(int, input().split())

    if a == 1:
        # update
        segment_tree_update(1, 1, n, b, c)
    if a == 2:
        # range
        print(segment_tree_rangemul(1, 1, n, b, c) % 1000000007)