[PS] 백준 11505번: 구간 곱 구하기

|

문제

내가 이해한 문제 내용

주어지는 쿼리에 대해서 업데이트를 하거나 구간 곱을 구하여라.

접근 방식

세그먼트 트리를 공부하고 라이님이 추천해주는 문제로 풀게 되었기 때문에 바로 세그먼트 트리를 사용했다. 아주 기초적으로 구간합 부분을 공부했지만 구간곱도 그냥 곱으로 바꾸고 모듈러를 취하는 것이기 때문에 그렇게 어렵진 않았지만 잔실수가 많았다.

어려웠던 점 & 배운 점

업데이트 함수를 짤 때 그 함수 내에서 업데이트를 적용시키려면 몫 연산자를 써야 하는데 이게 모듈러 연산자랑 같이 쓰일 경우 의도하지 않은 값이 도출될 수 있다. 따라서, 그냥 초기화를 할 때처럼 리프노드부터 bottom-up 방식으로 해주는게 제일 깔끔하다는 것을 배웠다. 그리고 계속 틀렸습니다가 뜰 때는 오버플로우가 발생하는지 꼭 확인하도록 하자…여기서 모듈러를 쓰기 때문에 발생하지 않을 줄 알았는데 여전히 발생해서 long long으로 바꿨더니 맞았다. 주의좀하자..

시간복잡도

쿼리의 개수가 $m+k$이고 세그먼트 트리의 초기화,구간곱,업데이트가 모두 $O(log_2n)$이므로 $O((m+k)log_2n)$이다.

코드

#include <cstdio>
#include <vector>
using namespace std;

typedef long long ll;

ll n,m,k,a,b,c;
const ll mod = 1000000007;
vector<ll> arr,tree;

ll init(ll node,ll s,ll e)
{
    if(s==e) return tree[node]=arr[s];
    return tree[node]=((init(node*2,s,(s+e)/2)%mod)*(init(node*2+1,(s+e)/2+1,e)%mod))%mod;
}

ll mul(ll node,ll s,ll e,ll l, ll r)
{
    if(s>r || e<l) return 1;
    if(s>=l && e<=r) return tree[node];
    return ((mul(node*2,s,(s+e)/2,l,r)%mod)*(mul(node*2+1,(s+e)/2+1,e,l,r)%mod))%mod;
}

ll update(ll node,ll s,ll e,ll index,ll value)
{
    if(index<s || index>e) return tree[node];
    if(s==e) return tree[node]=value;
    return tree[node]=((update(node*2,s,(s+e)/2,index,value)%mod)*
        (update(node*2+1,(s+e)/2+1,e,index,value)%mod))%mod;
}

int main(void)
{
    scanf("%lld%lld%lld",&n,&m,&k);
    arr.resize(n);
    tree.resize(4*n);

    for(ll i=0; i<n; i++) scanf("%lld",&arr[i]);
    init(1,0,n-1);
    
    for(ll i=0; i<m+k; i++){
        scanf("%lld%lld%lld",&a,&b,&c);
        if(a==1) update(1,0,n-1,b-1,c);
        else printf("%lld\n",mul(1,0,n-1,b-1,c-1)%mod);
    }
    return 0;
}