백준 / 11505 / 구간 곱 구하기 / 파이썬, python, pypy

11505번: 구간 곱 구하기

 

구간 합 구하기와 비슷한 방식으로 세그먼트 트리를 사용하면 될 것이라 생각했다.

 

각 tree의 값을 곱으로 계산하면 될 것이라 생각했지만, 

 

구간 합 구하기에서는 이전에 저장되어있던 수와 새로 바뀌는 수의 차이(diff)를 구해서 변경했지만,

 

곱에서는 0이 들어갈 경우 같은 방식으로 계산이 불가능 했다.

 

그래서 새로 값이 바뀔 경우 update에서 start == end라면 배열의 새로운 값을 넣고

 

아닐경우 start~mid, mid+1~end 구간으로 나누어서 쪼개 내려갔다.

 

세그먼트 트리를 알고있다면 쉽게 풀 수 있는 문제라고 생각된다.

 

import sys
import math
 
def init_tree(start, end, index):
    if start == end:
        tree[index] = arr[start]
    else:
        mid = (start + end) // 2
        tree[index] = init_tree(start, mid, 2*index) * init_tree(mid+1, end, 2*index + 1) % 1000000007
    return tree[index]
 
def find_mul(start, end, index, left, right):
    if left > end or right < start:
        return 1
    if left <= start and end <= right:
        return tree[index]
 
    mid = (start + end) // 2
    return find_mul(start, mid, 2*index, left, right) * find_mul(mid+1, end, 2*index + 1, left, right) % 1000000007
 
def update_tree(start, end, index, where, diff):
    if where < start or end < where:
        return
 
    if start == end:
        tree[index] = diff
    else:
        mid = (start + end) // 2
        update_tree(start, mid, index*2, where, diff)
        update_tree(mid+1, end, index*2 + 1, where, diff)
        tree[index] = tree[2*index] * tree[2*index + 1] % 1000000007
 
N, M, K = map(int, sys.stdin.readline().split())
arr = [int(sys.stdin.readline()) for _ in range(N)]
tree = [0] * (1 << (int(math.ceil(math.log2(N))) + 1))
init_tree(0, N-1, 1)
 
for _ in range(M + K):
    a, b, c = map(int, sys.stdin.readline().split())
 
    if a == 1: # 수 변경
        update_tree(0, N-1, 1, b-1, c)
 
    else: # elif a == 2: # 구간 곱 구하기
        print(find_mul(0, N-1, 1, b-1, c-1))