구간 곱 구하기

• 구간 합 구하기 문제에서 합을 곱(과 모듈러)으로 바꿨을 뿐이지만, 푸는 방법이 조금 차이가 생긴다
• 세그먼트 트리를 사용한다면, 동일한 방식으로 합만 곱으로 고쳐서 똑같이 모든 쿼리를 O(logn)에 해결가능하다.
• 그러나 펜윅 트리를 사용한다면, 곱은 합과 달리 역연산이 없기 때문에 그대로 적용할 수 없다.
  • 나누기가 역연산인 것 같지만, 곱한 수가 0일 경우에는 적용이 불가능하다.
• 범위 안에 0이 존재하는지만 체크하기 위한 펜윅트리를 따로 만들어서 처리하면 펜윅트리로도 가능하지만, 굳이 그렇게 구현하지는 않고, 그냥 세그먼트 트리로만 구현해서 풀었다.
• 트리를 구축하는 것에 O(n)이 걸리고, m+k개의 쿼리를 각각 O(logn)에 해결하므로, 전체 시간 복잡도는 O(n + (m+k)logn)
• 제출된 몇몇 코드는 똑같이 비재귀 세그트리로 구현했지만 내 코드보다 많이 빠르다. 이것은 매번 곱하기를 할때마다 모듈러를 하는 대신에, 곱하기를 두번 하고 나머지 연산을 한번 하는 식으로 구현되어서 그렇다. 나는 일반화된 구현을 그대로 가져다 쓰는것을 목표로 하고 있기에 그런 최적화까지는 적용하지 않았다.

"""Solution code for "BOJ 11505. 구간 곱 구하기".

- Problem link: https://www.acmicpc.net/problem/11505
- Solution link: http://www.teferi.net/ps/problems/boj/11505
"""

import sys
from teflib import segmenttree

MOD = 1_000_000_007


def main():
    N, M, K = [int(x) for x in sys.stdin.readline().split()]
    nums = [int(sys.stdin.readline()) for _ in range(N)]
    segtree = segmenttree.SegmentTree(nums, lambda x, y: x * y % MOD)
    for _ in range(M + K):
        a, b, c = [int(x) for x in sys.stdin.readline().split()]
        if a == 1:
            segtree.set(b - 1, c)
        else:
            print(segtree.query(b - 1, c))


if __name__ == '__main__':
    main()

• Dependency: teflib.segmenttree.SegmentTree