[BOJ] Q11505 구간 곱 구하기

[BOJ] Q11505 구간 곱 구하기

Question

Language: python

Difficulty: Gold 1

특정 구간의 곱에 대한 쿼리를 산발적으로 요청하기 때문에, Segment-Tree을 통해 구간 곱에 대해서 저장해서 쿼리를 처리한다. segment tree을 구현하는 부분을 공통적이나, 특정 인덱스의 값을 수정할 때, 0에서 다른 값으로 수정하는 경우가 발생하기 때문에 Top-Down 방식의 수정이 불가능하다. 따라서, 리프노드에서 부터 값을 수정하는 Bottom-up 형태로 수정을 처리해야된다.

기존의 Top-Down update

def update_value(index,start,end,change_index,diff):
    #범위 밖에 있는 경우
    if change_index < start or end < change_index:
        return
    tree[index]+=diff
    
    #리프 노드에 도달한 경우
    if start==end:
        return

    mid=(start+end)//2

    update_value(index*2,start,mid,change_index,diff)
    update_value(index*2+1,mid+1,end,change_index,diff)

Bottom-Up Update

def update(index,start,end,change_index,new_value):
    #범위에 포함되지 않는 경우
    if change_index < start or end < change_index:
        return tree[index]
    
    #리프 노드인 경우
    if start == end:
        tree[index]=new_value
        return new_value
    
    mid=(start+end)//2
    tree[index]=update(index*2,start,mid,change_index,new_value)*update(index*2+1,mid+1,end,change_index,new_value)% DIV

    return tree[index]

Solution

import sys

#세그멘트 트리를 초기화하는 함수
def init(index,start,end):
    #리프노드에 도달한 경우
    if start == end:
        tree[index]=datas[start-1]
        return tree[index]
    
    mid=(start+end)//2
    tree[index]=init(index*2,start,mid) * init(index*2+1,mid+1,end)% DIV
    return tree[index]

#특정 구간의 구간합을 구하기 위한 함수
def query(index,start,end,left,right):
    #범위에 포함되지 않는 구간인 경우 1을 반환
    if right < start or end < left:
        return 1
    #범위를 완전히 포함하고 있는 경우
    elif left <= start and end <=right:
        return tree[index]

    mid=(start+end)//2
    return query(index*2,start,mid,left,right) * query(index*2+1,mid+1,end,left,right)% DIV

#특정 인덱스의 값을 수정하기 위한 함수
def update(index,start,end,change_index,new_value):
    #범위에 포함되지 않는 경우
    if change_index < start or end < change_index:
        return tree[index]
    
    #리프 노드인 경우
    if start == end:
        tree[index]=new_value
        return new_value
    
    mid=(start+end)//2
    tree[index]=update(index*2,start,mid,change_index,new_value)*update(index*2+1,mid+1,end,change_index,new_value)% DIV

    return tree[index]

if __name__ == "__main__":
    input=sys.stdin.readline
    n,m,k=map(int,input().split())
    DIV = 1000000007
    
    datas=[int(input()) for _ in range(n)]
    queries=[map(int,input().split()) for _ in range(m+k)]
    
    tree=[0] * (4*n)
    init(1,1,n)
    for option, a, b in queries:
        #수 바꾸기
        if option == 1:
            update(1,1,n,a,b)
            datas[a-1]=b
            
        #쿼리
        if option == 2:
            print(query(1,1,n,a,b))