BOJ_11505_G1_구간곱구하기

문제 링크 : https://www.acmicpc.net/problem/11505

세그먼트 트리의 대표 문제인 구간 합 구하기 문제에서 합이 곱으로 변형된 문제이다.

세그먼트 트리의 전형적인 구조인

init(곱 트리 생성)

mul(구간 곱 계산)

update(말단 노드 최신화)

이 세 가지 함수를 사용해서 구할 수 있다.

---

핵심 포인트

1. 구간 곱이기 때문에 문제에서 곱의 값이 10억 7 보다 클 경우 10억 7로 mod 연산을 요구하였다.

2. 구간 합과는 다르게 구간 곱은 0이란 숫자가 있으면 해당 노드가 포함된 구간은 모두 0으로 변경된다.

3. update 함수를 구현할 시 구간 합일 경우 propagation 방식으로 코드를 작성할 수 있다. 하지만 구간곱의 경우 propagation으로 작성 시 10억 7보다 값이 커져서 mod 연산을 한 숫자에 대해서 정확한 값을 구할 수 없게 되므로 재귀 방식으로 update 함수를 작성해야 한다.