[segment tree] 11505번 구간 곱 구하기

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

자료구조

• segment tree

풀이

포인트

• segment tree 자료구조를 이용해서 $O(logn)$ 시간 복잡도로 문제 풀기 (segment tree 자료구조 설명)
• modular 연산에 유의하여 update 함수 변경하기

segment tree

update 함수

기존의 누적 합 문제에서는 새로 바꿀 수와 기존의 수와의 차이 (diff)를 구하고, 해당 인덱스가 포함되는 노드에 diff를 더해주는 식으로 update 함수가 작동했다. 하지만 이 문제에서는 누적 곱을 구하는 문제이고 중간에 modular 연산이 들어가기 때문에 이런 방식으로 할 수가 없다. 만약에 누적합 문제와 유사하게 누적곱의 update 함수를 구성하면 아래와 같을 것이다.

def update(node, start, end, index, old, new):
    if not (start <= index <= end):
        return
    tree[node] /= old
    tree[node] *= new
    tree[node] = int(tree[node])
    tree[node] %= __div__
    if start != end:
        update(node*2, start, (start+end)//2, index, old, new)
        update(node*2 + 1, (start+end)//2 + 1, end, index, old, new)

• 기존의 수 (old)를 나눠주고, 대체할 수 (new)을 곱해줘서 해당 노드의 값을 업데이트한다.
• 그리고 modular 계산을 수행한다.

어떤 노드 값이 $2^{30}$ 이라고 하자. modular 계산에 의해서 해당 노드 값은 $2^{30} \ mod \ 1000000007 = 73741817$이 된다. 여기에 2를 나눠본다고 하자. 그러면 그 값이 $2^{29}$와 달라지는 것을 알 수 있다. 따라서 위와 같이 바꿔주려는 인덱스를 포함하는 노드에 연산을 해주는 것이 아니라, 우선 leafnode까지 가서 노드의 값을 바꿔주고 다시 해당 노드와 연결된 모든 노드를 업데이트하는 식으로 함수를 짜야한다.

def update(node, start, end, index, old, new):
    if not (start <= index <= end):
        return
    elif start == end:
        tree[node] = new
        return
    update(node * 2, start, (start + end) // 2, index, old, new)
    update(node * 2 + 1, (start + end) // 2 + 1, end, index, old, new)

    tree[node] = tree[node*2] * tree[node*2 + 1] % __div__

• elif 구문에서 leafnode의 값을 바꿔준다.
• if와 elif에 모두 걸리지 않는다는 것은, 해당 인덱스가 노드에 포함하면서 leafnode가 아니라는 뜻이다.
• 이때, leafnode의 값을 업데이트 해준 이후이므로 해당 노드의 값을 변경하고 modular 계산을 수행한다.

init, subsum 함수

여기서도 modular 계산을 주의해야한다. (a*b)%c = ((a%c)*(b%c))%c임을 기억하자.

• init 함수에서 if 문에 걸려서 반환하는 부분과 최종 반환하는 부분에 modular 계산을 수행하였다.
• subsum 함수에서 if 문에 걸려서 반환하는 부분에 modular 계산을 수행하였다.
• 두 재귀 함수의 반환 값을 곱하는 것은 결국 if 문에서 반환하는 값들을 곱하는 것이고, 따라서 이들에 대해 modular 계산을 수행하는 것이 (a%c)*(b%c)을 하는 것과 같다.
• 마지막 반환 값에 modular 계산을 수행하는 것은 ((a%c)*(b%c))%c을 하는 것과 같다.

[Source Code]

from math import log2, ceil
import sys
input = sys.stdin.readline
__div__ = 1000000007

def init(node, start, end):
    if start == end:
        tree[node] = l[start]
        return tree[node] % __div__
    tree[node] = (init(node*2, start, (start+end)//2)) * \
                 (init(node*2 + 1, (start+end)//2 + 1, end))
    return tree[node] % __div__

def subsum(node, start, end, left, right):
    if left <= start and end <= right:
        # print(tree[node],node)
        return tree[node] % __div__
    if end < left or right < start:
        return 1
    return ((subsum(node*2, start, (start+end)//2, left, right)) * \
           (subsum(node*2 + 1, (start+end)//2 + 1, end, left, right)))

def update(node, start, end, index, old, new):
    if not (start <= index <= end):
        return
    elif start == end:
        tree[node] = new
        return

    update(node * 2, start, (start + end) // 2, index, old, new)
    update(node * 2 + 1, (start + end) // 2 + 1, end, index, old, new)

    tree[node] = tree[node*2] * tree[node*2 + 1] % __div__

n,m,k = map(int,input().split())
h = int(ceil(log2(n)))
tree = [0]*(2**(h+1))
l = []
for _ in range(n):
    l.append(int(input()))

init(1, 0, n-1)

for _ in range(m+k):
    a,b,c = map(int,input().split())
    if a == 1:
        b -= 1
        old = l[b]
        new = c
        l[b] = new
        update(1, 0, n-1, b, old, new)
    if a == 2:
        b -= 1
        c -= 1
        print(subsum(1, 0, n-1, b, c) % __div__)