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

문제

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

11505번: 구간 곱 구하기

 

풀이

배열이 주어지고 배열의 구간의 대한 값을 물어보는 문제입니다. 값을 가져오는 것 말고도 변경하는 작업도 해야하기 때문에 구간합과 같은 배열을 이용하기 보단, 세그먼트 트리를 이용해야 합니다.

 

세그먼트 트리의 구현에 대한 문제이므로 세그먼트 트리를 먼저 공부한 뒤 푸는것이 좋습니다.

 

이 문제에서 주의할 점은 구간의 곱을 구하기 때문에 구간을 벗어나는 노드인 경우 0이 아닌 1을 리턴해야 합니다.
곱셈이기 때문에 0을 리턴해버리면 이후 모든 곱셈연산이 0을 결과로 가지게됩니다.

int getMul(pair<int, int> range, int idx, int start, int end)
{
    if (end < range.first || range.second < start)
        return 1;
    
    if (range.first <= start && end <= range.second)
        return tree[idx];
    
    int mid = (start + end) / 2;
    return (uint64_t)getMul(range, idx*2 + 1, start, mid) * getMul(range, idx*2 + 2, mid+1, end) % MOD;
}

 

 

각 노드의 값은 1,000,000,007로 나눈 나머지 값을 저장하므로 32비트로 표현이 가능합니다.
하지만 부모 노드의 값을 계산하기 위해 두 자식 노드의 값을 곱할때 오버플로우가 발생해버리기 때문에 이에 대한 처리가 필요합니다.

 

간단하게 노드의 자료형 크기를 64비트로 선언하여 곱할때의 오버플로우를 해결할 수 있고,

또는 곱셈 연산을 할 때 형변환을 해주어 오버플로우를 해결할 수 있습니다.

return tree[idx] = (uint64_t)init() * init() % MOD;

 

 

코드

#include <iostream>
#include <vector>
#include <cmath>

#define MOD 1000000007

using namespace std;

int n, m, k;
int height;
int treeSize;
vector<uint64_t> arr;
vector<uint64_t> tree;

uint64_t init(int idx, int start, int end)
{
    if (start == end)
        return tree[idx] = arr[start];
    
    int mid = (start + end) / 2;
    tree[idx] = init(idx*2 + 1, start, mid) * init(idx*2 + 2, mid + 1, end) % MOD;
    return tree[idx] ;
}

uint64_t getMul(pair<int, int> range, int idx, int start, int end)
{
    if (end < range.first || range.second < start)
        return 1;
    
    if (range.first <= start && end <= range.second)
        return tree[idx];
    
    int mid = (start + end) / 2;
    return getMul(range, idx*2 + 1, start, mid) * getMul(range, idx*2 + 2, mid+1, end) % MOD;
}

uint64_t update(int num, int target, int idx, int start, int end)
{
    // if (start == end && target == start)
    //     return tree[idx] = num;

    if (target < start || end < target) // 반드시 이 조건 먼저 확인
        return tree[idx];

    if (start == end)
        return tree[idx] = num;

    int mid = (start + end) / 2;
    return tree[idx] = update(num, target, idx*2 + 1, start, mid) * update(num, target, idx*2 + 2, mid+1, end) % MOD;
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> n >> m >> k;
    arr.resize(n);
    height = ceil(log2(n));
    treeSize = (1 << (height+1) )-1;
    tree.resize(treeSize, 0);
    for (int i=0; i<n; ++i)
    {
        cin >> arr[i];
    }

    init(0, 0, n-1);

    for (int i=0; i< m+k; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        if (a == 1)
        {
            update(c, b-1, 0, 0, n-1);
        }
        else
        {
            cout << getMul({b-1, c-1}, 0, 0, n-1) << "\n";
        }
    }

    return 0;
}