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

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

구간 합 구하기(백준 2042) 문제와 유사하지만 update 함수 구현이 조금 더 복잡했다.

구간 합의 경우 트리 update시 연산이 비교적 단순하다. 바꾸려는 index가 포함된 tree들에 기존 값을 빼고 바꾸려는 값을 더하면 된다.

그러나 구간곱의 경우, 위와 같은 방식을 사용해서 이전값을 나누고 바꾸는 값을 곱하는 연산을 하면 오답이 발생한다.

tree[node] = (tree[node]/orv*chv)%MOD;

첫번째로 orv==0 인 경우 에러가 발생하고, 두번째로 모듈러 연산에서는 나머지로 연산하기 때문에 기대하는 값과 다른 값으로 계산될 수 있다.

따라서 해당 문제는 바꾸려는 index의 값을 바꾼 후, 다시 tree들이 재연산되도록 구현해야 풀 수 있다.

void updateTree(int start, int end, int index, int node, ll chv){

    if(index<start || index>end) return ;
   // tree[node] = (tree[node]/orv*chv)%MOD;
    if(start==end) {
        tree[node]=chv;
        return ;
    }
    int mid = (start+end)/2;

    if(index<=mid) updateTree(start, mid, index, node*2, chv);
    else updateTree(mid+1, end, index, node*2+1, chv);

    tree[node] = (tree[2*node] * tree[2*node+1]) % MOD;

    return;

}