[ 백준 ] 11505번 - 구간 곱 구하기 (C++)

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

11505번: 구간 곱 구하기

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 읽고 오시면 좋습니다!!

https://rudalsd.tistory.com/51?category=1073064 

[ 자료구조 ] 세그먼트 트리 (Segment Tree)

https://rudalsd.tistory.com/45?category=1064608 

[ 알고리즘 ] 모듈러 연산(Modular Arithmetic)

 

정답의 범위가 int의 범위를 벗어나므로 long long 자료형을 써주어야 합니다. 또한, 1,000,000,007로 나눈 나머지 값을 출력해야 하므로 모듈러 연산에 대해서도 알고 있으면 좋습니다.

 

일반적인 세그먼트 트리와는 다르게 숫자를 0으로 바꾸면 0으로 나누어지는 경우가 생길 수도 있으므로 숫자를 바꿀 때 이 점 유의하셔야 합니다.

 

[ 소스 코드 ]

 

#include<iostream>
#include<vector>
#include<cmath>
 
#define ll long long
#define MOD 1000000007
 
using namespace std;
 
int N, M, K;
vector<ll> segTree;
ll arr[1000001];
 
ll makeTree(int node, int start, int end)        //트리 만들기
{
    if (start == end) return segTree[node] = arr[start];
    int mid = (start + end) / 2;
 
    ll left = makeTree(node * 2, start, mid);    //왼쪽 자식 노드
    ll right = makeTree(node * 2 + 1, mid + 1, end);    //오른쪽 자식 노드
 
    return segTree[node] = ((left % MOD) * (right % MOD)) % MOD;
}
 
ll gopTree(int node, int start, int end, int sidx, int eidx)    //sidx ~ eidx 사이의 곱
{
    if (end < sidx || start > eidx) return 1;    //범위를 벗어나면
    if (sidx <= start && eidx >= end) return segTree[node];    //범위에 완전히 포함되면
    //범위에 일부 포함되면
    int mid = (start + end) / 2;
 
    ll left = gopTree(node * 2, start, mid, sidx, eidx);    //왼쪽 자식 노드
    ll right = gopTree(node * 2 + 1, mid + 1, end, sidx, eidx);    //오른쪽 자식 노드
 
    return ((left % MOD) * (right % MOD)) % MOD;
}
 
ll changeTree(int node, int start, int end, int idx)
{
    if (idx < start || idx > end) return segTree[node];    //idx가 범위에 포함되지 않으면
    if (start == end) {                //바꾸고자 하는 노드에 도착하면
        return segTree[node] = arr[idx];
    }
    //idx가 범위에 포함되면
    int mid = (start + end) / 2;
 
    ll left = changeTree(node * 2, start, mid, idx);    //왼쪽 자식 노드
    ll right = changeTree(node * 2 + 1, mid + 1, end, idx);    //오른쪽 자식 노드
 
    return segTree[node] = ((left % MOD) * (right % MOD)) % MOD;
    
}
 
int main()
{
    cin >> N >> M >> K;
 
    for (int i = 1; i <= N; i++) {
        scanf("%lld", &arr[i]);
    }
 
    int size = (1 << (int)(ceil(log2(N)) + 1));    //트리 사이즈 구하기
    segTree.resize(size);
    makeTree(1, 1, N);        //트리 만들기
 
    for (int i = 0; i < M + K; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
 
        if (a == 1) {        //숫자 바꾸기
            arr[b] = (ll)c;
            changeTree(1, 1, N, b);
        }
        else {                //구간 곱 구하기
            ll ans = gopTree(1, 1, N, b, c);
            ans %= MOD;
            printf("%lld\n", ans);
        }
    }
}