[백준 11505] 구간 곱 구하기

 

 세그먼트 트리 문제이다. 전체적인 맥락은 세그먼트 트리를 이용해 구간 합을 구하고 수정하는 문제와 유사하지만, 곱 연산이 들어가고 입력으로 주어지는 수에 0이 존재할 수 있기 때문에 구간 합 문제보다 까다로운 문제가 된다.

 

[백준 2042] 구간 합 구하기 (tistory.com)

[백준 2042] 구간 합 구하기

 

 

 트리를 초기화하는 부분과 값을 가져오는 함수는 문제 조건에 맞춰 모듈러 연산이 더해진 것 말고는 구간 합 문제와 같다. 위에서 언급했듯이, 까다로운 것은 0의 존재로 인한 값 수정 처리인데 입력으로 0이 주어지지 않는다면 그냥 기존 값으로 나누고 새로운 값을 곱해서 손쉽게 구할 수 있었을 것이다. 하지만 0이 존재하기 때문에, 기존 값이 0인 경우 0으로 나누는 Arithmetic Error가 발생해 버리므로 해당 로직을 사용할 수 없다.

 

 

 

 입력받은 수의 배열의 크기가 8이고, 루트의 인덱스가 1인 구간 곱 세그먼트 트리의 각 인덱스가 나타내는 범위는 일반적으로 위와 같을 것이다.

 

  

 만약, 4번째 수가 0이었다고 하면 4번째 수를 포함하는 범위의 구간 곱은 모두 0이 되어버린다. 그리고 4번째 수를 다른 양의 정수로 수정하는 작업이 필요하다고 할 때, 4번째 수를 포함하는 구간과 아닌 구간으로 나누어서 생각해볼 수 있다. 트리의 1번 노드처럼 해당 수를 포함하는 구간의 경우, 값이 수정되면 당연히 구간 곱도 바뀔 수 있다. 따라서 트리를 초기화할 때처럼, 구간을 절반으로 쪼개어 각각의 구간 곱 값을 곱한 값을 이용한다.

 이 때, 절반으로 쪼갠 구간 또한 값의 수정이 필요한 상태이므로, 재귀적인 실행을 통해 하위 구간 수정하는 함수를 먼저 실행할 수 있도록 한다. 

 그러면 2번 노드와 3번 노드에 대한 수정 함수가 콜 되는데, 2번 노드 같은 경우엔 1번 노드의 케이스와 같고 3번 노드는 1번 노드와 달리 구간에 수정이 필요한 값이 포함되어 있지 않다. 따라서 3번 노드처럼, 구간에 수정할 값이 포함되어 있지 않은 경우 기존에 가지고 있던 구간 곱 값을 그대로 리턴한다.

 재귀를 이어나가면 결국 11번 노드에 대한 수정 함수가 콜 되는데, 더 이상 하위 구간이 없는 길이 1짜리 구간을 나타내고 있으므로 이때가 재귀 종료 조건이 된다. 이 시점에, 해당 노드의 구간 곱 값을 바꾸려는 값 그 자체로 바꾸고 리턴한다.

 이후에는 재귀 구조에 따라, 이제 변경된 구간 곱 값이 하위 노드에서 상위 노드로 리턴되며 올바르게 변경된 값이 반영될 것이다.

 

 

 좀 지저분하지만, 굳이 순서를 표시하자면 위와 같이 될 것이다. 초록색 화살표는 recursive call이고, 주황색 화살표는 값의 리턴이다.

 

 위 로직을 반영해 작성한 코드는 아래와 같다. 은근히 실수하기 좋은 부분이 많은 문제였다.

 

#include <iostream>
#include <vector>
#define MOD 1000000007

using namespace std;

vector<long long> segTree;
vector<long long> arr;

long long makeTree(int l, int r, int ind) {
    if(l==r) {
        segTree[ind] = arr[l];
        return segTree[ind];
    } else {
        int mid = (l+r)/2;
        segTree[ind] = makeTree(l, mid, ind*2) * makeTree(mid+1, r, ind*2+1) % MOD;
        return segTree[ind];
    }
}

long long getMulti(int l, int r, int ind, int lBound, int rBound) {
    if(l>rBound || r<lBound) return 1;
    if(l>=lBound && r<=rBound) return segTree[ind];

    int mid = (l+r)/2;
    return getMulti(l, mid, ind*2, lBound, rBound) * getMulti(mid+1, r, ind*2+1, lBound, rBound) % MOD;
}

long long update(int l, int r, int ind, int target, int newNum) {
    if(target<l || target>r) return segTree[ind];
    if(l==r) return segTree[ind] = newNum;
    
    int mid = (l+r)/2;
    return segTree[ind] = update(l, mid, ind*2, target, newNum) * update(mid+1, r, ind*2+1, target, newNum) % MOD;
}

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

    int n, m, k;
    cin >> n >> m >> k;

    segTree = vector<long long>(n*4);
    arr = vector<long long>(n+1);

    for(int i=1; i<=n; i++) {
        cin >> arr[i];
    }

    makeTree(1, n, 1);

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