세그먼트 트리 응용1 - 구간의 곱을 구하는 세그먼트 트리

1. 문제

 

11505번: 구간 곱 구하기 (acmicpc.net)

11505번: 구간 곱 구하기

 

특정 구간의 합을 구하라는 것에서 특정 구간의 곱을 구하는 것으로 바뀜

 

근데 구간의 합을 구하는 것에서 몇가지 살짝? 신경써야함

 

 

2. 풀이

 

기본적으로 트리의 노드에 왼쪽 자식과 오른쪽 자식의 합을 저장하던 것을 왼쪽 자식과 오른쪽 자식의 곱을 저장하는 것으로 바꾸면 된다

 

tree[tree_index] = tree[2*tree_index] * tree[2*tree_index+1]

 

그런데 몇가지 생각을 조금 해야함

 

 

다이나믹 프로그래밍 정복기5 -피보나치 수열은 왜 n으로 나눠도 문제가 없는가? - (tistory.com)

다이나믹 프로그래밍 정복기5 -피보나치 수열은 왜 n으로 나눠도 문제가 없는가? -

 

먼저 구간의 곱을 1000000007로 나눈 나머지를 출력하라고 했는데 

 

"a를 n으로 나눈 나머지와 b를 n으로 나눈 나머지의 곱을 n으로 나눈 나머지는 a*b를 n으로 나눈 나머지와 같다"

 

라는 사실을 이용해서 시간을 단축해야함

 

세그먼트 트리에 구간의 곱을 저장할때, 왼쪽 자식과 오른쪽 자식의 곱을 1000000007로 나눈 나머지를 저장해줘야함

 

(안그러면 시간초과)

 

 

-------------------------------------------------------------------------------------------------------------------------------------

 

그리고 update함수를 2가지를 배웠는데..

 

하나는 A[index] = value로 바꾸면 원래 합에 value - A[index]를 더하면 바꿀 수 있다는 점을 이용해서

 

index가 [start,end]에 포함되면 tree_index에 저장된 값에 value - A[index]를 더해서 바꾸는 방법

 

def update_tree(tree,tree_index,start,end,index,difference):
    
    #index가 [start,end]에 포함되지 않는 경우
    
    if index < start or index > end:
        
        return
    
    #index가 포함되는 구간이라면.. 해당 노드의 값을 바꿔줌
    tree[tree_index] = tree[tree_index] + difference
    
    #리프노드가 아닌 경우, 왼쪽,오른쪽 자식으로 탐색함
    
    mid = (start + end) // 2
    
    if start != end:
        
        update_tree(tree,2*tree_index,start,mid, index, difference)
        update_tree(tree,2*tree_index+1,mid+1,end,index,difference)

def update(A,tree,N,index,value):
    
    difference = value - A[index] #합을 변경시킬 값
    
    A[index] = value #index값이 value로 바뀜
    
    update_tree(tree,1,0,n-1,index,difference) #루트부터 탐색해서 값이 바뀐다

 

그런데 구간의 곱을 구할때 얘를 쓰면 어떻게 해야될지 문제다

 

A[index] = value로 바꾸면..

 

특정 구간의 곱이 s * A[index]에서 s * value로 바뀔건데

 

그러면 difference를 value/A[index]로 정의해서 하면 될것 같은데

 

하지만 입력으로 주어지는 수가 0보다 크거나 같고 1000000보다 작거나 같은 정수라니까..

 

애초에 A[index]가 0이라면.. value/A[index]가 정의가 안되니까.. 

 

이게 difference로 뭘 써야할지 문제

 

def update(A,tree, tree_index, start, end, index, value):
    
    #index가 [start,end]에 포함되어 있지 않다
    
    if index < start or index > end:
        
        return
    
    #리프노드를 찾았다면... 값을 바꿔준다
    
    if start == end:
        
        A[index] = value
        tree[tree_index] = value
        return
    
    #리프노드가 아니라면, 왼쪽, 오른쪽으로 나누어서 탐색
    
    mid = (start + end) // 2
    
    update(A,tree,2*tree_index, start, mid, index, value)
    update(A,tree,2*tree_index+1,mid+1,end, index, value)
    
    #update 함수가 return되면 자식 노드의 값들은 변경되어 있다
    tree[tree_index] = tree[2*tree_index] + tree[2*tree_index+1]

 

그래서 두번째 update방법도 알아야겠다..(하나만 알려고 했는데)

 

두번째 방법은 leaf node를 만나면 A[index] = value로 바꾸고 tree[tree_index] = value로 바꿔준다음에...

 

재귀함수 호출이 끝나면 return되면서 자식노드가 모두 바뀌어 있으니까, 이를 이용해서 부모 노드의 값도 바꾸는 방법

 

-------------------------------------------------------------------------------------------------------------------------------------------------------

 

모두 구간의 곱으로 수정해서 만든 구간의 곱을 구하는 세그먼트 트리는..

 

import math
from sys import stdin

def create_segment(A,tree,tree_index,A_start,A_end):
    
    if A_start == A_end:
        
        tree[tree_index] = A[A_start]
    
    else:
        
        A_mid = (A_start+A_end)//2
        create_segment(A,tree,2*tree_index,A_start,A_mid)
        create_segment(A,tree,2*tree_index+1,A_mid+1,A_end)
        
        #곱을 1000000007로 나눈 나머지를 저장

        tree[tree_index] = (tree[2*tree_index] * tree[2*tree_index+1]) % 1000000007
  
def query_product(tree,tree_index,start,end,left,right):
    
    if left > end or right < start:
        
        return 1
    
    if left <= start and end <= right:
        
        return tree[tree_index]
    
    mid = (start+end)//2

    left_product = query_product(tree,2*tree_index,start,mid,left,right)
    right_product = query_product(tree,2*tree_index+1,mid+1,end,left,right)
    
    #곱을 1000000007로 나눈 나머지를 저장
    
    return (left_product*right_product)% 1000000007

def update(A,tree,tree_index,start,end,index,value):
    
    if index < start or index > end:
        
        return
    
    if start == end:
        
        A[index] = value
        tree[tree_index] = value
        return
    
    mid = (start+end)//2
    
    update(A,tree,2*tree_index,start,mid,index,value)
    update(A,tree,2*tree_index+1,mid+1,end,index,value)
    
    #곱을 1000000007로 나눈 나머지를 저장

    tree[tree_index] = (tree[2*tree_index]*tree[2*tree_index+1])% 1000000007
    

N,m,k = map(int,stdin.readline().split())

A = []

for _ in range(N):
    
    a = int(stdin.readline())

    A.append(a)

n = 2**(math.ceil(math.log2(N))+1)-1

tree = [0]*(n+1)

create_segment(A,tree,1,0,N-1)

for _ in range(m+k):
    
    a,b,c = map(int,stdin.readline().split())

    if a == 1:
        
        update(A,tree,1,0,N-1,b-1,c)
    
    elif a == 2:
        
        print(query_product(tree,1,0,N-1,b-1,c-1))