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

문제

접근 방법

세그먼트 트리를 사용하는 문제이다.
구간 합이 아닌 구간 곱을 구하는 문제로 구간 합을 구하는 세그먼트 트리와 유사하게 작성하면 된다.

코드

#include <iostream>
#include <vector>
using namespace std;
typedef unsigned long long ull;
vector<int> nums;
vector<ull> tree;
ull init(int start, int end, int node)
{
    if (start == end)
        return tree[node] = nums[start];
    int mid = (start + end) >> 1;
    int nextNode = node << 1;
    ull l = init(start, mid, nextNode);
    ull r = init(mid + 1, end, nextNode | 1);
    return tree[node] = (l * r) % 1000000007;
}
void update(int start, int end, int node, int target, int num)
{
    if (start > target || end < target)
        return;
    if (start == target && end == target)
    {
        tree[node] = num;
        return;
    }
    int mid = (start + end) >> 1;
    int nextNode = node << 1;
    if (start != end)
    {
        update(start, mid, nextNode, target, num);
        update(mid + 1, end, nextNode | 1, target, num);
    }
    tree[node] = (tree[nextNode] * tree[(nextNode | 1)]) % 1000000007;
}
ull find(int start, int end, int node, int left, int right)
{
    if (start > right || end < left)
        return 1;
    if (start >= left && end <= right)
    {
        return tree[node];
    }
    int mid = (start + end) >> 1;
    int nextNode = node << 1;
    ull l = find(start, mid, nextNode, left, right);
    ull r = find(mid + 1, end, nextNode | 1, left, right);
    return (l * r) % 1000000007;
}
int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0);
    int N, M, K;
    cin >> N >> M >> K;
    nums = vector<int>(N + 1);
    tree = vector<ull>((N << 2), 1);
    for (int i = 1; i <= N; ++i)
    {
        cin >> nums[i];
    }
    init(1, N, 1);
    for (int i = 0; i < M + K; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        if (a == 1)
        {
            update(1, N, 1, b, c);
        }
        else
        {
            cout << find(1, N, 1, b, c) << "\n";
        }
    }
    return 0;
}

풀이

정직하게도 2번 예제에서 잘못된 경우를 확인할 수 있게 해준다. 바로 차이점을 이용해 수정하는 방법의 문제이다.
만약 0으로 수정하였을 경우 구간 내의 모든 곱이 0으로 초기화된다. 그 상태에서 다시 차이점을 이용해 수정하려 해도 0에 무엇을 곱해도 0이 되기에 불가능해진다.

즉 수정을 하려면 해당 b번째 수를 c로 변경해준 뒤 다시 거슬러 올라가며 자식들을 곱해주어야 한다는 것이다.

그렇게 하면 0으로 변경됐을지라도 값이 변하면 다시 곱하여 덮어 씌어주기에 2번 예제의 경우를 해결해준다.